Skip to main content

Graph

Connected Components​

547. Number of Provinces​

547. Number of Provinces

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
disjoint_set = DisjointSets(n)
 
for row in range(n):
for col in range(row + 1, n):
if isConnected[row][col]:
disjoint_set.union(row, col)
 
return disjoint_set.getCount()

323. Number of Connected Components in an Undirected Graph​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
disjoint_set = DisjointSets(n)
for a, b in edges:
disjoint_set.union(a, b)
return disjoint_set.getCount()

1971. Find if Path Exists in Graph​

1971. Find if Path Exists in Graph

Easy1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def validPath(
self, n: int, edges: List[List[int]], source: int, destination: int
) -> bool:
disjoint_sets = DisjointSets(n)
for a, b in edges:
disjoint_sets.union(a, b)
return disjoint_sets.find(source) == disjoint_sets.find(destination)

1101. The Earliest Moment When Everyone Become Friends​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def earliestAcq(self, logs: List[List[int]], n: int) -> int:
disjoint_set = DisjointSets(n)
logs.sort(key=lambda i: i[0])
 
for timestamp, a, b in logs:
disjoint_set.union(a, b)
if disjoint_set.getCount() == 1:
return timestamp
return -1

1319. Number of Operations to Make Network Connected​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
if len(connections) < n - 1:
return -1
disjoint_sets = DisjointSets(n)
for a, b in connections:
disjoint_sets.union(a, b)
return disjoint_sets.getCount() - 1

Cycle Detection​

261. Graph Valid Tree​

261. Graph Valid Tree

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
disjoint_set = DisjointSets(n)
 
for a, b in edges:
if not disjoint_set.union(a, b):
return False
 
return disjoint_set.getCount() == 1

684. Redundant Connection​

684. Redundant Connection

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
disjoint_sets = DisjointSets(1001)
result = None
for a, b in edges:
if not disjoint_sets.union(a, b):
result = [a, b]
return result

Component Size​

Journey to the Moon​

Journey to the Moon

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

def journeyToMoon(n, astronaut):
disjoint_sets = DisjointSets(n)
for a, b in astronaut:
disjoint_sets.union(a, b)
result = math.comb(n, 2)
for root, count in disjoint_sets.getSizes():
result -= math.comb(count, 2)
return result

Merging Communities ​

Merging Communities

Hard1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

n, q = map(int, input().split())
disjoint_sets = DisjointSets(n + 1)
for _ in range(q):
op, i, *j = input().split()
if op == "M":
disjoint_sets.union(int(i), int(j[0]))
else:
print(disjoint_sets.getSize(int(i)))

Components in a graph​

Components in a graph

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

def componentsInGraph(gb):
disjoint_sets = DisjointSets(2 * len(gb) + 1)
for a, b in gb:
disjoint_sets.union(a, b)
mini, maxi = float("inf"), -float("inf")
for root, size in disjoint_sets.getSizes():
if size >= 2:
mini = min(mini, size)
maxi = max(maxi, size)
return [mini, maxi]

Advanced Applications​

1202. Smallest String With Swaps​

1202. Smallest String With Swaps

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
disjoint_sets = DisjointSets(len(s))
for a, b in pairs:
disjoint_sets.union(a, b)
components = collections.defaultdict(list)
for idx, char in enumerate(s):
root = disjoint_sets.find(idx)
components[root].append(char)
for comp in components:
components[comp] = sorted(components[comp], reverse=True)
result = []
for idx in range(len(s)):
root = disjoint_sets.find(idx)
result.append(components[root].pop())
return "".join(result)

721. Accounts Merge​

721. Accounts Merge

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
disjoint_sets = DisjointSets(len(accounts))
email_idx = {}
for idx, (name, *emails) in enumerate(accounts):
for email in emails:
if email not in email_idx:
email_idx[email] = idx
disjoint_sets.union(email_idx[emails[0]], email_idx[email])
 
merged_accounts = collections.defaultdict(list)
for email, idx in email_idx.items():
root = disjoint_sets.find(idx)
merged_accounts[root].append(email)
results = []
for root in merged_accounts:
results.append([accounts[root][0], *sorted(merged_accounts[root])])
return results

947. Most Stones Removed with Same Row or Column​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
size = 20002
disjoint_sets = DisjointSets(size)
is_stone = [False] * size
for row, col in stones:
col += 10001
disjoint_sets.union(row, col)
is_stone[row] = is_stone[col] = True
components = sum(
is_stone[i] and disjoint_sets.find(i) == i for i in range(size)
)
return len(stones) - components

737. Sentence Similarity II​

737. Sentence Similarity II

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def areSentencesSimilarTwo(
self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]
) -> bool:
disjoint_sets = DisjointSets(2 * len(similarPairs))
pair_idx = {}
for idx, (a, b) in enumerate(similarPairs):
pair_idx.setdefault(a, 2 * idx)
pair_idx.setdefault(b, 2 * idx + 1)
disjoint_sets.union(pair_idx[a], pair_idx[b])
for word1, word2 in zip(sentence1, sentence2):
if word1 != word2:
a = pair_idx.get(word1, None)
b = pair_idx.get(word2, None)
if a is None or b is None:
return False
if disjoint_sets.find(a) != disjoint_sets.find(b):
return False
return len(sentence1) == len(sentence2)

990. Satisfiability of Equality Equations​

Medium1 solutionexplanationanalysis1 playground
Solutions:

Explanation

Analysis

class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
disjoint_sets = DisjointSets(ord("z") + 1)
for a, eq, _, b in equations:
if eq == "=":
disjoint_sets.union(ord(a), ord(b))
for a, eq, _, b in equations:
if eq == "!" and disjoint_sets.find(ord(a)) == disjoint_sets.find(ord(b)):
return False
return True