Number of Provinces
给一个无向图, 求几个强连通组件.
并查集的例题.
class Solution {
public int findCircleNum(int[][] isConnected) {
int size = isConnected.length;
DSU dsu = new DSU(size);
for(int i = 0; i < isConnected.length; i++) {
for(int j = 0; j < isConnected.length; j++) {
if(isConnected[i][j] == 1){
dsu.union(i, j);
}
}
}
Set<Integer> set = new HashSet<>();
for(int i = 0; i < size; i++) {
set.add(dsu.get(i));
}
return set.size();
}
class DSU{
int[] p;
public DSU(int size) {
this.p = new int[size];
for(int i = 0; i < size; i++) {
p[i] = i;
}
}
int get(int v) {
if(p[v] == v)
return v;
return p[v] = get(p[v]);
}
boolean union(int a, int b) {
a = get(a);
b = get(b);
if(a == b)
return false;
p[a] = b;
return true;
}
}
}