1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public int countComponents(int n, int[][] edges) {
Map<Integer, Set<Integer>> nodeEntry = new HashMap<>();
for (int[] edge : edges) {
nodeEntry.putIfAbsent(edge[0], new HashSet<>());
nodeEntry.get(edge[0]).add(edge[1]);
nodeEntry.putIfAbsent(edge[1], new HashSet<>());
nodeEntry.get(edge[1]).add(edge[0]);
}
Set<Integer> visited = new HashSet<>();
int ans = 0;
for (int i = 0; i < n; i++) {
if (!visited.contains(i)) {
if (nodeEntry.containsKey(i)) {
dfs(i, nodeEntry, visited);
}
ans += 1;
}
}
return ans;
}
private void dfs(int node, Map<Integer, Set<Integer>> nodeEntry, Set<Integer> visited) {
visited.add(node);
Set<Integer> neighbors = nodeEntry.get(node);
for (Integer neighbor : neighbors) {
if (!visited.contains(neighbor)) {
dfs(neighbor, nodeEntry, visited);
}
}
}
}
|
最基础的DFS做法.
时间复杂度: O(N) n个nodes.
空间复杂度: O(N) 可能是skewed graph.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution {
private static class UnionFind {
private int[] parent;
private int[] rank;
private int count;
private UnionFind(int size) {
parent = new int[size];
rank = new int[size];
count = size;
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
rank[i] = 1;
}
}
private int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
private void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot != yRoot) {
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot] += 1;
}
count -= 1;
}
}
private int getCount() {
return count;
}
}
public int countComponents(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
return uf.count;
}
}
|
Union Find.
时间复杂度: O(V) V是edge的个数, 也就是我们做union的次数.
空间复杂度: O(n) 我们new了UnionFind类型的object, 里面装了两个长度为n的array.
