LeetCode 323. 【Java】【LOCK】323. Number of Connected Components in an Undirected Graph
原题链接
中等
作者:
tt2767
,
2020-03-18 21:25:52
,
所有人可见
,
阅读 906
/** 求无向图的连通分量
1. dfs: 0~n-1 中每找到一个未被标记的点, count++, 并且沿此点标记能到达的所有点
2. 并查集: 直接合并所有点, 返回block 数即可
*/
class Solution {
class UnionFindSet{
int[] pre;
int size, block;
public UnionFindSet(int n){
pre = new int[n];
size = n;
block = n;
for (int i = 0 ; i < n ; i ++) pre[i] = i;
}
public int find(int x){
if (pre[x] != x) pre[x] = find(pre[x]);
return pre[x];
}
public boolean union(int x, int y){
int fx = find(x);
int fy = find(y);
if (fx == fy) return false;
pre[fx] = fy;
block--;
return true;
}
}
public int countComponents(int n, int[][] edges) {
return merge(n, edges);
// return search(n, edges);
}
public int merge(int n, int[][] edges){
UnionFindSet ufs = new UnionFindSet(n);
for (int i = 0; i < edges.length ; i ++){
ufs.union(edges[i][0], edges[i][1]);
}
return ufs.block;
}
public int search(int n, int[][] edges){
boolean[] visit = new boolean[n];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0 ; i < n ; i ++) graph.add(new ArrayList<Integer>());
for (int i = 0; i < edges.length; i++){
int x = edges[i][0];
int y = edges[i][1];
graph.get(x).add(y);
graph.get(y).add(x);
}
int count = 0;
for (int i = 0 ; i < n ; i++){
if (!visit[i]){
count ++ ;
dfs(i, visit, graph);
}
}
return count;
}
private boolean dfs(int x, boolean[] visit, List<List<Integer>> graph){
if (visit[x]) return false;
visit[x] = true;
List<Integer> edge = graph.get(x);
for (int i = 0 ; i < edge.size(); i ++){
int y = edge.get(i);
dfs(y, visit, graph);
}
return true;
}
}