1. 題目很簡單，只要求出每個(gè)連通分量有多少個(gè)節(jié)點(diǎn)即可
2. 首先通過建立一個(gè)字典來表示每個(gè)節(jié)點(diǎn)的鄰接關(guān)系
3. 遍歷每個(gè)節(jié)點(diǎn)，并通過鄰接關(guān)系標(biāo)記在當(dāng)前連通分量內(nèi)的所有的點(diǎn)，這樣就可以知道一個(gè)連通分量內(nèi)有多少個(gè)點(diǎn)
4. 在這里我陷入了一個(gè)誤區(qū)，導(dǎo)致最后超時(shí)，我一開始把所有的連通分量的點(diǎn)數(shù)都求出來之后，再將他們兩兩組合得到最后的答案（耗時(shí)O(a²) 其中a是連通分量的數(shù)量），而事實(shí)上對(duì)于每個(gè)連通分量它的組合數(shù)就是 cnt * (n - cnt) 只要 O(a) 就可以求出來，最后由于每一個(gè)點(diǎn)對(duì)都被計(jì)算了兩次，因此需要 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 = 0for i in range(n):if i in isCnt:continuecnt = 1l = d[i]isCnt.add(i)while len(l) > 0:newl = []for j in l:if j in isCnt:continuenewl.extend(d[j])cnt += 1isCnt.add(j)l = newl.copy()ans += cnt * (n - cnt)return ans // 2