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
| class Solution {
public long countPairs(int n, int[][] edges) {
boolean[] visited = new boolean[n];
Map<Integer, List<Integer>> neighbors = new HashMap<>();
for (int[] edge : edges) {
neighbors.computeIfAbsent(edge[0], (key) -> new ArrayList<>()).add(edge[1]);
neighbors.computeIfAbsent(edge[1], (key) -> new ArrayList<>()).add(edge[0]);
}
long ans = 0, remainingNodes = n;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
long groupSize = dfs(i, neighbors, visited);
ans += groupSize * (remainingNodes - groupSize);
remainingNodes -= groupSize;
}
}
return ans;
}
private int dfs(int currNode, Map<Integer, List<Integer>> neighbors, boolean[] visited) {
visited[currNode] = true;
int ans = 1;
if (!neighbors.containsKey(currNode)) {
return ans;
}
for (Integer neighbor : neighbors.get(currNode)) {
if (!visited[neighbor]) {
ans += dfs(neighbor, neighbors, visited);
}
}
return ans;
}
}
|
思路很简单, 统计每个小团体node的个数. 然后计算每个小团体的node个数乘以剩余的node个数, 就是这个小团体的不可达的pair的个数. 然后把所有小团体的不可达的pair的个数加起来就是答案. 这个思路很重要, 我之前想的是把所有的小团体的个数统计记录, 然后使用nested for loop来计算每个小团体的不可达的pair的个数, 这样的话时间复杂度是O(n^2), 会超时. 这个思路是O(n), 但是我还是没想出来. 这里的思路是知道第一个小团体的groupSize后, 这个size乘上剩下的node的个数就是能和第一个小团体中node构成pair的个数. 为了防止重复计算, 我们把第一个小团体的node个数从remaningNodes中减去. 之后是得到第二个小团体的groupSize,
同样乘以剩余node的个数(此时的个数已经抛去第一个小团体的node). 这个方法是O(n)时间复杂度的.
时间复杂度: O(n + m), n是node的个数, m是edge的个数. 创建map需要O(m), visited数组是O(n).
空间复杂度: O(n + e) map + visited数组.
