每日一题 2316. 统计无向图中无法互相到达点对数（中等，图连通分量）

1. 题目很简单，只要求出每个连通分量有多少个节点即可
2. 首先通过建立一个字典来表示每个节点的邻接关系
3. 遍历每个节点，并通过邻接关系标记在当前连通分量内的所有的点，这样就可以知道一个连通分量内有多少个点
4. 在这里我陷入了一个误区，导致最后超时，我一开始把所有的连通分量的点数都求出来之后，再将他们两两组合得到最后的答案（耗时O(a²) 其中a是连通分量的数量），而事实上对于每个连通分量它的组合数就是 cnt * (n - cnt) 只要 O(a) 就可以求出来，最后由于每一个点对都被计算了两次，因此需要 ans // 2

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        d = defaultdict(list)
        isCnt = set()
        for i in range(len(edges)):
            d[edges[i][0]].append(edges[i][1])
            d[edges[i][1]].append(edges[i][0])
        ans = 0
        for i in range(n):
            if i in isCnt:
                continue
            cnt = 1
            l = d[i]
            isCnt.add(i)
            while len(l) > 0:
                newl = []
                for j in l:
                    if j in isCnt:
                        continue
                    newl.extend(d[j])
                    cnt += 1
                    isCnt.add(j)
                l = newl.copy()
            ans += cnt * (n - cnt)
        return ans // 2
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