Disjoint-set and Connected components
- Number of Connected Components in an Undirected Graph
- Number of Island
- Couple holding hands (hard) 這個題目我覺得graph信息很隱藏 需要認真思考才能想到，作為難題很合格。
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
0 3
| |
1 --- 2 4
Output: 2
Example 2:
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 4
| |
1 --- 2 --- 3
Output: 1
Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
先簡陋的寫一點解法， 之後再polish。
- Union-Find
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
# union-find
parent = [i for i in range(n)]
def union(x, y):
parent_x = find(x)
parent_y = find(y)
if parent_x != parent_y:
parent[parent_x] = parent_y
def find(x):
return x if parent[x] == x else find(parent[x])
# by rank:
rank = [1] * n
def union_by_rank(x, y):
parent_x = find(x)
parent_y = find(y)
if rank[parent_x] < rank[parent_y]:
# parent x 比較高級 把 y歸給x
parent[parent_x] = parent_y
elif rank[parent_x] > rank[parent_y]:
parent[parent_y] = parent[x]
else: #要是他倆rank相等 隨便放一個 然後當孩子的rank + 1
parent[parent_x] = parent_y
rank[parent_y] += 1
for i, j in edges:
union(i, j)
parent_count = 0
for i, v in enumerate(parent):
if i == v: # if p is the parent, if a disconnected graph multiple parents can happen
parent_count += 1
return parent_count
- DFS & BFS
DFS和BFS解這種題的思想差不多是， 一次DFS可以找到一組set， 每個vertex都放進去DFS， 就可以找到所有disjoint set的總數。（稍後畫個圖來說）
# DFS
def countComponents(self, n: int, edges: List[List[int]]) -> int:
def build_graph():
for x, y in edges:
graph[x] = y
graph[y] = x
visited = set()
def dfs(node, visited):
visited.add(node)
for n in graph[node]:
if n not in visited:
dfs(n, visited)
count = 0
for node in range(n):
if node not in visited:
dfs(node)
count += 1
return count
Couple holding hands
N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.
The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).
The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.
Example 1:
Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
這個題記錄兩個方法吧。
Greedy
Greedy的方法很好理解，雖然我不知道如何證明，而且我也不會證明。
就從前往後兩個兩個一組看，假如row[i] 和row[i+1]是一對兒，就continue loop， 否則的話就繼續往後找，直到找到跟當前 i是一對兒的index j , 然後swap i+1 和 j。
這裡學到的trick是用和1 XOR 操作 來判斷row[i] 和 row[i+1] 是不是一對couple。
簡單來說異或XOR對於even number 相當於加 1， 對於 odd number 是減 1。 因為偶數的最後一個bit是0， 而奇數的最後一個bit 是1。
舉個🌰
XOR 規律 不一樣的是1 一樣的是0
1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
2 ^ 1 in binary: 10 ^ 01 ==> 11 ==> 3
3 ^ 1 in binary: 11 ^ 01 ==> 10 ==> 2
Number of connected components in a graph
這個的巧妙想法是，把每一組couch當做是一個component。比如
0123， 01是一個component (couch one）, 23是另一個component (couch two)。然後我們就發現當所有的couple都在自己的位置上的時候， 每一個component (couch)都是獨立存在的互不干涉，於是就沒有connected component。 然而當couple位置錯亂的時候， 比如0213， couch one has an element from couch two (2 in this case), and couch two has an element from couch one. In this scenario, we consider couch one and couch two connected, hence we need one swap to "disconnect" these two couches. It became clear that this problem is a classic graph disjoint-set problem. The number of swaps needed is simply equivalent to the total number of connected components in this "couch" graph. We can solve this problem using either Union-Find or DFS (methods mentioned above).
After figuring out what was actually asked in this problem, we know we need to build a graph to solve this. Here comes another crux: how do we build this graph. As we mentioned before, each couch is a "component" and there are two elements in each component. In order to figure out the connectivity between couches, we need to know which element belongs to which couch. For example, 0 and 1 are on couch one, 2 and 3 are on couch two. How can we build the mapping? The **trick ** is to divide the element value by 2. (just like an easy hashing mechanism ), so that 0 and 1 go to a same bucket, 2 and 3 go to a different bucket. This way we will have N / 2 number of components.
Union-Find Approach
# Time complexity O(logN)
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
# find connected component
number_of_couches = int(len(row) / 2)
self.ans = 0 # number of connected component
def union(x, y):
x_p = find(x)
y_p = find(y)
if x_p != y_p:
parent[y_p] = parent[x_p]
self.ans += 1
def find(x):
return x if parent[x] == x else find(parent[x])
# only N/2 couch
parent = [i for i in range(number_of_couches)]
for i in range(0, len(row), 2):
couch_one = int(row[i] / 2)
couch_two = int(row[i+1] / 2)
union(couch_one, couch_two)
return self.ans
DFS Approach
DFS approach relies on building a graph. The rest is just a standard DFS template to find all disconnected sets.
How to build this graph
def build_graph(row):
graph = collections.defaultdict(list)
for i in range(len(row), 2):
first_couch = int(row[i] / 2)
second_couch = int(row[i+1] / 2)
if fisrt_couch != second_couch:
graph[first_couch].append(second_couch)
graph[second_couch].append(first_couch)
def dfs(node):
if not node:
# will come back to finish this later.
网友评论