給出一個無向圖，問其中一共有多少個節(jié)點對是不連通的，用DFS出每個連通分量的節(jié)點數(shù)暴力搞過了，最后計數(shù)的部分要這么稍稍優(yōu)化一下不然TLE
用并查集應(yīng)該會更快
1 #2316
2 #Runtime: 2121 ms (Beats 54.5%)
3 #Memory: 114.9 MB (Beats 16.22%)
4
5 class Solution(object):
6 def countPairs(self, n, edges):
7 """
8 :type n: int
9 :type edges: List[List[int]]
10 :rtype: int
11 """
12 edge = defaultdict(list)
13 for x, y in edges:
14 edge[x].append(y)
15 edge[y].append(x)
16 vis = [0] * n
17
18 def DFS(node):
19 vis[node] = 1
20 self.tp += 1
21 for y in edge[node]:
22 if not vis[y]:
23 DFS(y)
24
25 ncc = []
26 ans = 0
27 for i in range(n):
28 if not vis[i]:
29 self.tp = 0
30 DFS(i)
31 ncc.append(self.tp)
32 total = 0
33 for j in range(len(ncc)):
34 ans += (n - total - ncc[j]) * ncc[j]
35 total += ncc[j]
36 return ans