分量的数目【中等】Plus"/>
Leetcode—323.无向图中连通分量的数目【中等】Plus
2023每日刷题(七)
Leetcode—323.无向图中连通分量的数目
方法一:并查集思路实现代码
static int father[2010] = {0};int Find(int x) {if(x != father[x]) {father[x] = Find(father[x]);}return father[x];
}void Union(int x, int y) {int a = Find(x);int b = Find(y);if(a != b) {father[a] = b;}
}int countComponents(int n, int** edges, int edgesSize, int* edgesColSize){int i;for(i = 0; i < n; i++) {father[i] = i;}*edgesColSize = 2;int x = 0, y = 0;int j;for(i = 0; i < edgesSize; i++) {j = 0;x = edges[i][j];y = edges[i][j+1];Union(x, y);}int ans = 0;for(i = 0; i < n; i++) {if(i == Find(i)) {ans++;}}return ans;
}
复杂度分析
测试结果
方法二:DFS找连通分量
在无向图中,连通分量是一个子图,其中每对顶点都通过一条路径连接。因此,本质上,连通分量中的所有顶点都是相互可以到达的。 让我们看看如何使用 DFS 来解决这个问题。如果我们从一个特定的顶点开始运行 DFS,它将继续深度优先访问顶点,直到没有更多的相邻顶点可以访问为止。因此,它将访问包含起始顶点的连通分量中的所有顶点。每次我们完成一个连通分量的探索,我们可以找到一个 还未被访问过的 顶点,并从那里开始新的 DFS。开始新的 DFS 的次数就是连通分量的数量。 下面是一个示例来说明这个方法
实现代码
class Solution {
public:void dfs(vector<int> &visited, vector<int> adjList[], int num) {// 更新为已被访问visited[num] = 1;int j;for(j = 0; j < adjList[num].size(); j++) {if(visited[adjList[num][j]] == 0) {dfs(visited, adjList, adjList[num][j]);}}}int countComponents(int n, vector<vector<int>>& edges) {int ans = 0;if(n == 0) {return 0;}// 邻接矩阵vector<int> adjList[n];vector<int> visited(n, 0);int i = 0;// 初始化邻接矩阵for(; i < edges.size(); i++) {adjList[edges[i][0]].push_back(edges[i][1]);adjList[edges[i][1]].push_back(edges[i][0]);}for(i = 0; i < n; i++) {if(visited[i] == 0) {ans++;dfs(visited, adjList, i);}}return ans;}
};
测试结果
之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!
更多推荐
Leetcode—323.无向图中连通分量的数目【中等】Plus
发布评论