-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcount_unreachable_pairs_of_nodes_in_an_undirected_graph.py
135 lines (110 loc) · 4.39 KB
/
count_unreachable_pairs_of_nodes_in_an_undirected_graph.py
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
'''
You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
Return the number of pairs of different nodes that are unreachable from each other.
'''
'''
* Make groups of nodes which are connected
eg., edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
0 ---- 2 1 --- 6 3
| |
| |
5 ---- 4
groups will be {0: 4, 1: 2, 3: 1},
i.e 4 nodes are present in group0, 2 nodes are present in group1 and 1 node is present in group3
* Now, we have [4, 2, 1] as no of nodes in each group, we have to multiply each of no. with remaining
ans = (4 * 2 + 4 * 1) + (2 * 1)
but calculating ans this way will give TLE.
* if we notice, (4 * 2 + 4 * 1) + (2 * 1), we can combine, equation like this,
4 * 2 + (4 + 2) * 1, using this, we can reduce complexity.
so, if we have count of groups array as [a, b, c, d], ans will be,
ans = a * b + (a + b) * c + (a + b + c) * d
* will use, union for generating groups.
* ps, you can modify UnionFind class as per your need. Have implemented full union-find for beginners.
'''
class UnionFind:
def __init__(self, size):
self.root = [i for i in range(size)]
self.rank = [1] * size
def find(self, x):
if x == self.root[x]:
return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.root[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.root[rootX] = rootY
else:
self.root[rootY] = rootX
self.rank[rootX] += 1
class Solution:
def countPairs(self, n: int, edges: List[List[int]]) -> int:
dsu = UnionFind(n)
for u, v in edges:
dsu.union(u, v)
C = Counter([dsu.find(i) for i in range(n)])
groupCounts = list(C.values())
ans = 0
firstGroupCount = groupCounts[0]
for i in range(1, len(groupCounts)):
ans += firstGroupCount * groupCounts[i]
firstGroupCount += groupCounts[i]
return ans
--------------------------------------------------------------------------------------
class Solution:
def countPairs(self, n: int, edges: List[List[int]]) -> int:
def dfs(graph,node,visited):
visited.add(node)
self.c += 1
for child in graph[node]:
if child not in visited:
dfs(graph, child, visited)
#build graph
graph = {}
for i in range(n):
graph[i] = []
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
totalNodes = 0
#run dfs in unvisited nodes
for i in range(n):
if i not in visited:
self.c = 0
dfs(graph, i, visited)
count += totalNodes*self.c # result
totalNodes += self.c # total nodes visited
return count
-----------------------------------------------------------------------------------------------------------------------------------
class Solution:
def countPairs(self, n: int, edges: List[List[int]]) -> int:
def dfs(graph,node,visited):
visited.add(node)
self.c += 1
for child in graph[node]:
if child not in visited:
dfs(graph, child, visited)
#build graph
graph = {}
for i in range(n):
graph[i] = []
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
totalNodes = 0
#run dfs in unvisited nodes
for i in range(n):
if i not in visited:
self.c = 0
dfs(graph, i, visited)
count += totalNodes*self.c # result
totalNodes += self.c # total nodes visited
return count