Graph

Connected Components

547. Number of Provinces

547. Number of Provinces

Medium1 solutionexplanationanalysis1 playground

---

Solutions:

Explanation

Interactive Visualization

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

323. Number of Connected Components in an Undirected Graph

Medium1 solutionexplanationanalysis1 playground

---

Solutions:

Explanation

Interactive Visualization

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

Interactive Visualization

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

1101. The Earliest Moment When Everyone Become Friends

Medium1 solutionexplanationanalysis1 playground

---

Solutions:

Explanation

Interactive Visualization

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

1319. Number of Operations to Make Network Connected

Medium1 solutionexplanationanalysis1 playground

---

Solutions:

Explanation

Interactive Visualization

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

Interactive Visualization

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

Interactive Visualization

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

Interactive Visualization

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

Interactive Visualization

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

Interactive Visualization

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

Interactive Visualization

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

Interactive Visualization

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

947. Most Stones Removed with Same Row or Column

Medium1 solutionexplanationanalysis1 playground

---

Solutions:

Explanation

Interactive Visualization

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

Interactive Visualization

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

990. Satisfiability of Equality Equations

Medium1 solutionexplanationanalysis1 playground

---

Solutions:

Explanation

Interactive Visualization

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

---