圖論實戰題解

# python
# LC 323 - Number of Connected Components in an Undirected Graph
# IDEA: build an undirected adjacency list; each DFS launched from an unvisited node is one component
# time = O(V + E), space = O(V + E)
from collections import defaultdict

def countComponents(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)          # undirected: both directions
    visited = set()
    count = 0
    for start in range(n):
        if start in visited:
            continue
        count += 1                  # an unvisited node opens a new component
        visited.add(start)
        stack = [start]
        while stack:
            node = stack.pop()
            for nxt in graph[node]:
                if nxt not in visited:
                    visited.add(nxt)
                    stack.append(nxt)
    return count

# countComponents(5, [[0,1],[1,2],[3,4]]) -> 2

# python
# LC 133 - Clone Graph
# IDEA: DFS; copies = {original: copy} doubles as visited; wire each copy's neighbours from the recursion
# time = O(V + E), space = O(V)
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    copies = {}                         # original -> its copy
    def dfs(cur):
        if cur in copies:
            return copies[cur]
        copy = Node(cur.val)
        copies[cur] = copy              # register BEFORE recursing, or a cycle recurses forever
        for nxt in cur.neighbors:
            copy.neighbors.append(dfs(nxt))
        return copy
    return dfs(node) if node else None

# python
# LC 947 - Most Stones Removed with Same Row or Column
# IDEA: union ("row", r) with ("col", c) for each stone; answer = stones - components
# time = O(n log n) with path halving alone, space = O(n)
def removeStones(stones):
    parent = {}
    def find(x):
        parent.setdefault(x, x)
        while parent[x] != x:
            parent[x] = parent[parent[x]]      # path halving
            x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
    for r, c in stones:
        union(("row", r), ("col", c))          # the stone IS the edge row r -- column c
    roots = {find(("row", r)) for r, c in stones}
    return len(stones) - len(roots)

# [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] -> 5   (one component of 6 stones)
# [[0,0],[0,2],[1,1],[2,0],[2,2]]       -> 3   (components of 4 and 1 stones)

// java
// LC 947 - Most Stones Removed with Same Row or Column
// IDEA: union the stone's row with the stone's column (~col keeps the two id spaces apart)
// time = O(n log n) with path halving alone, space = O(n)
import java.util.*;

class Solution {
    private Map<Integer, Integer> parent = new HashMap<>();

    private int find(int x) {
        parent.putIfAbsent(x, x);
        while (parent.get(x) != x) {
            parent.put(x, parent.get(parent.get(x)));   // path halving
            x = parent.get(x);
        }
        return x;
    }

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) {
            parent.put(ra, rb);
        }
    }

    public int removeStones(int[][] stones) {
        parent = new HashMap<>();
        for (int[] s : stones) {
            union(s[0], ~s[1]);          // row id = r, column id = ~c (negative, never a row)
        }
        Set<Integer> roots = new HashSet<>();
        for (int[] s : stones) {
            roots.add(find(s[0]));
        }
        return stones.length - roots.size();
    }
}