Leetcode1971. 寻找图中是否存在路径

Every day a Leetcode

题目来源：1971. 寻找图中是否存在路径

解法1：并查集

并查集介绍：并查集详解

代码：

/** @lc app=leetcode.cn id=1971 lang=cpp** [1971] 寻找图中是否存在路径*/// @lc code=start
class UnionFind
{vector<int> father, size;public:UnionFind(int n) : father(n), size(n, 1){// iota函数可以把数组初始化为 0 到 n-1iota(father.begin(), father.end(), 0);}int find(int x){if (x == father[x])return x;elsereturn find(father[x]);}void connect(int p, int q){int fa_p = find(p), fa_q = find(q);if (fa_p != fa_q)father[fa_p] = fa_q;}bool isConnected(int p, int q){return find(p) == find(q);}
};class Solution
{
public:bool validPath(int n, vector<vector<int>> &edges, int source, int destination){UnionFind uf(n);for (vector<int> &edge : edges)uf.connect(edge[0], edge[1]);return uf.isConnected(source, destination);}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n+m×α(m))，其中 n 是图中的顶点数，m 是图中边的数目，α 是反阿克曼函数。并查集的初始化需要 O(n) 的时间，然后遍历 m 条边并执行 m 次合并操作，最后对 source 和 destination 执行一次查询操作，查询与合并的单次操作时间复杂度是 O(α(m))，因此合并与查询的时间复杂度是 O(m×α(m))，总时间复杂度是 O(n+m×α(m))。

空间复杂度：O(n)，其中 n 是图中的顶点数。并查集需要 O(n) 的空间。

解法2：深度优先搜索

首先从顶点 source 开始遍历并进行递归搜索。搜索时每次访问一个顶点 vertex 时，如果 vertex 等于 destination 则直接返回，否则将该顶点设为已访问，并递归访问与 vertex 相邻且未访问的顶点 next。如果通过 next 的路径可以访问到 destination，此时直接返回 true，当访问完所有的邻接节点仍然没有访问到 destination，此时返回 false。

代码：

class Solution
{
public:bool dfs(int source, int destination, vector<vector<int>> &adj, vector<bool> &visited){if (source == destination){return true;}visited[source] = true;for (int next : adj[source]){if (!visited[next] && dfs(next, destination, adj, visited)){return true;}}return false;}bool validPath(int n, vector<vector<int>> &edges, int source, int destination){vector<vector<int>> adj(n);for (auto &edge : edges){int x = edge[0], y = edge[1];adj[x].emplace_back(y);adj[y].emplace_back(x);}vector<bool> visited(n, false);return dfs(source, destination, adj, visited);}
};

结果：

复杂度分析：

时间复杂度：O(n+m)，其中 n 表示图中顶点的数目，m 表示图中边的数目。

空间复杂度：O(n+m)，其中 n 表示图中顶点的数目，m 表示图中边的数目。空间复杂度主要取决于邻接顶点列表、记录每个顶点访问状态的数组和递归调用栈，邻接顶点列表需要 O(m+n) 的存储空间，记录每个顶点访问状态的数组和递归调用栈分别需要 O(n) 的空间。