LeetCode 2421. Number of Good Paths - Disjoint set (Union Find) - Python 3 - for Coding Interviews

[alicecodeland]

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 numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:

edge = defaultdict(list)
for s, e in edges:
edge[s].append(e)
edge[e].append(s)

val_nodes = defaultdict(list)
for i, v in enumerate(vals):
val_nodes[v].append(i)

res = 0
ufo = UnionFind(len(vals))
for value, nodes in sorted(val_nodes.items()):
for node in nodes:
for neighbor in edge[node]:
if vals[node] >= vals[neighbor]:
ufo.union(node, neighbor)

group = defaultdict(int)
for node in nodes:
group[ufo.find(node)] += 1
for k, v in group.items():
res += v*(v+1)//2

return res