Skip to content
Gallery
Algoschool
Algocircle
Share
Explore
Level 1

DSU problems


⁠
https://leetcode.com/problems/number-of-islands
⁠
⁠
class DSU:
def __init__(self, items):
self.p = [i for i, _ in enumerate(items)]
self.rank = [0 for i in range(len(items))]
def union(self, x, y):
if x == y:
return
x = self.find(x)
y = self.find(y)
if self.rank[x] < self.rank[y]:
x, y = y, x
self.p[y] = x
if self.rank[x] == self.rank[y]:
self.rank[y] += 1
def find(self, x):
if self.p[x] == x:
return x
self.p[x] = self.find(self.p[x])
return self.p[x]

class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
dsu = DSU([i for i in range(len(grid) * len(grid[0]))])
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == '1':
n = i * len(grid[0]) + j
for (ix, jx) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
ni, nj = i + ix, j + jx
if ni < 0 or nj < 0 or ni >= len(grid) or nj >= len(grid[i]):
continue
if grid[ni][nj] == '1':
nx = ni * len(grid[0]) + nj
dsu.union(n, nx)
n = 0
for i, x in enumerate(dsu.p):
if i == x and grid[x // len(grid[0])][x % len(grid[0])] == '1':
n += 1
return n

⁠
https://leetcode.com/problems/number-of-provinces/submissions/
⁠
⁠
class DSU:
def __init__(self, items):
self.p = [i for i, _ in enumerate(items)]
self.rank = [0 for i in range(len(items))]
def union(self, x, y):
if x == y:
return
x = self.find(x)
y = self.find(y)
if self.rank[x] < self.rank[y]:
x, y = y, x
self.p[y] = x
if self.rank[x] == self.rank[y]:
self.rank[y] += 1
def find(self, x):
if self.p[x] == x:
return x
self.p[x] = self.find(self.p[x])
return self.p[x]
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
dsu = DSU([i for i in range(len(isConnected))])
for i in range(len(isConnected)):
for j in range(len(isConnected[i])):
if isConnected[i][j]:
dsu.union(i, j)
n = 0
for (i, x) in enumerate(dsu.p):
if i == x:
n += 1
return n


⁠
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
⁠
⁠
class DSU:
def __init__(self, items):
self.p = [x for x in items]
self.rank = [0 for x in items]
def find(self, x):
if self.p[x] == x:
return x
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.rank[x] < self.rank[y]:
x, y = y, x
self.p[y] = x
if self.rank[x] == self.rank[y]:
self.rank[x] += 1
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
dsu = DSU(list(range(n)))
for (i, j) in edges:
dsu.union(i, j)

res = 0
for i, x in enumerate(dsu.p):
if i == x:
res += 1
return res
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.