圖論實戰：5 題打通 DFS／BFS／拓撲排序／Union-Find（LC 200/207/133/547/269）

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'                       # sink it (mark visited)
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

void dfs(vector<vector<char>>& grid, int r, int c) {
    int rows = grid.size(), cols = grid[0].size();
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0';                           // sink it
    dfs(grid, r+1, c); dfs(grid, r-1, c);
    dfs(grid, r, c+1); dfs(grid, r, c-1);
}
int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int count = 0;
    for (int r = 0; r < grid.size(); r++)
        for (int c = 0; c < grid[0].size(); c++)
            if (grid[r][c] == '1') { count++; dfs(grid, r, c); }
    return count;
}

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * numCourses
    for course, pre in prerequisites:
        graph[pre].append(course)              # pre → course
        indegree[course] += 1
    q = deque(i for i in range(numCourses) if indegree[i] == 0)
    seen = 0
    while q:
        node = q.popleft()
        seen += 1
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    return seen == numCourses                  # all taken → no cycle

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> indegree(numCourses, 0);
    for (auto& p : prerequisites) {
        graph[p[1]].push_back(p[0]);           // pre → course
        indegree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < numCourses; i++)
        if (indegree[i] == 0) q.push(i);
    int seen = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        seen++;
        for (int nxt : graph[node])
            if (--indegree[nxt] == 0) q.push(nxt);
    }
    return seen == numCourses;                  // no cycle
}

def cloneGraph(node):
    if not node:
        return None
    clones = {}
    def dfs(n):
        if n in clones:                        # already cloned → reuse
            return clones[n]
        copy = Node(n.val)
        clones[n] = copy                       # register BEFORE recursing
        for nei in n.neighbors:
            copy.neighbors.append(dfs(nei))
        return copy
    return dfs(node)

Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    unordered_map<Node*, Node*> clones;
    function<Node*(Node*)> dfs = [&](Node* n) -> Node* {
        if (clones.count(n)) return clones[n]; // reuse
        Node* copy = new Node(n->val);
        clones[n] = copy;                      // register before recursing
        for (Node* nei : n->neighbors)
            copy->neighbors.push_back(dfs(nei));
        return copy;
    };
    return dfs(node);
}

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]      # path compression
            x = parent[x]
        return x
    def union(a, b):
        parent[find(a)] = find(b)
    for i in range(n):
        for j in range(i + 1, n):              # upper triangle
            if isConnected[i][j]:
                union(i, j)
    return sum(1 for i in range(n) if find(i) == i)

class DSU {
public:
    vector<int> parent;
    DSU(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;                              // path compression
    }
    void unite(int a, int b) { parent[find(a)] = find(b); }
};
int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    DSU dsu(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (isConnected[i][j]) dsu.unite(i, j);
    int count = 0;
    for (int i = 0; i < n; i++) if (dsu.find(i) == i) count++;
    return count;
}

from collections import deque

def alienOrder(words):
    graph = {c: set() for w in words for c in w}
    indegree = {c: 0 for c in graph}
    for first, second in zip(words, words[1:]):
        for a, b in zip(first, second):
            if a != b:                         # first differing char → edge
                if b not in graph[a]:
                    graph[a].add(b)
                    indegree[b] += 1
                break
        else:                                  # no diff in the shared prefix
            if len(second) < len(first):       # prefix violation → invalid
                return ""
    q = deque(c for c in indegree if indegree[c] == 0)
    res = []
    while q:
        c = q.popleft()
        res.append(c)
        for nxt in graph[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    return ''.join(res) if len(res) == len(graph) else ""   # cycle → ""

string alienOrder(vector<string>& words) {
    unordered_map<char, unordered_set<char>> graph;
    unordered_map<char, int> indegree;
    for (auto& w : words)
        for (char c : w) { graph[c]; indegree[c]; }   // register all chars
    for (int i = 0; i + 1 < (int)words.size(); i++) {
        string& a = words[i]; string& b = words[i+1];
        int len = min(a.size(), b.size()), j = 0;
        for (; j < len; j++) {
            if (a[j] != b[j]) {                        // first differing char
                if (!graph[a[j]].count(b[j])) {
                    graph[a[j]].insert(b[j]);
                    indegree[b[j]]++;
                }
                break;
            }
        }
        if (j == len && a.size() > b.size()) return "";   // prefix violation
    }
    queue<char> q;
    for (auto& [c, d] : indegree) if (d == 0) q.push(c);
    string res;
    while (!q.empty()) {
        char c = q.front(); q.pop();
        res += c;
        for (char nxt : graph[c])
            if (--indegree[nxt] == 0) q.push(nxt);
    }
    return res.size() == graph.size() ? res : "";        // cycle → ""
}