Questions
Medium
Hard
Solutions
Medium
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
def find(i: int) -> int:
if parent[i] != i:
parent[i] = find(parent[i])
return parent[i]
def union(*pair):
px, py = map(find, pair)
if px != py:
if rank[px] > rank[py]:
px, py = py, px
parent[px] = py
if rank[px] == rank[py]:
rank[py] += 1
parent = list(range(n))
rank = [0] * n
for edge in edges:
x, y = map(find, edge)
if x == y: return False
union(x, y)
return len(edges) == n - 1
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
def find(x: int) -> int:
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(*pair: tuple) -> None:
px, py = map(find, pair)
if px != py:
if rank[px] > rank[py]: px, py = py, px
parent[px] = py
rank[py] += int(rank[px] == rank[py])
parent = list(range(n))
rank = [0] * n
for u, v in edges:
union(u, v)
return len(set(find(i) for i in range(n)))
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(i: int) -> None:
seen.add(i)
for j, connected in enumerate(isConnected[i]):
if connected and j not in seen:
dfs(j)
n, ans = len(isConnected), 0
seen = set()
for i in range(n):
if i not in seen:
dfs(i)
ans += 1
return ans