跳轉到

Graph

Tarjan Algorithm

Tarjan algorithm 常用來判斷一條邊是否是圖中不可替代的連接。這裡以 bridge / critical connection 為例：如果移除某條邊後，原本連通的部分會被切開，那條邊就是 bridge。

Tarjan algorithm 的核心是 DFS order 和 low-link。dfn[u] 表示節點 u 第一次被拜訪的時間，low[u] 表示從 u 的 DFS 子樹出發，能透過 tree edge 或 back edge 到達的最小 dfn。

在無向圖中，若 DFS tree edge cur -> next 滿足 low[next] > dfn[cur]，代表 next 的子樹無法透過其他邊回到 cur 或更早的祖先，因此這條邊是 bridge，也就是 critical connection。

時間複雜度

  • Tarjan bridge / critical edge：O(V + E)

模板

C++
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> criticalConnections(
        int n,
        vector<vector<int>>& connections
    ) {
        vector<vector<pair<int, int>>> adj(n);

        for (int i = 0; i < (int)connections.size(); ++i) {
            int u = connections[i][0];
            int v = connections[i][1];

            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        vector<int> dfn(n, -1);
        vector<int> low(n, 0);
        vector<vector<int>> ans;
        int timer = 0;

        auto dfs = [&](auto&& dfs, int cur, int parent_edge) -> void {
            dfn[cur] = low[cur] = timer++;

            for (auto [next, edge_id] : adj[cur]) {
                if (edge_id == parent_edge) continue;

                if (dfn[next] == -1) {
                    dfs(dfs, next, edge_id);
                    low[cur] = min(low[cur], low[next]);

                    if (low[next] > dfn[cur]) {
                        ans.push_back({cur, next});
                    }
                } else {
                    low[cur] = min(low[cur], dfn[next]);
                }
            }
        };

        for (int i = 0; i < n; ++i) {
            if (dfn[i] == -1) {
                dfs(dfs, i, -1);
            }
        }

        return ans;
    }
};

參考題型

Eulerian Path / Circuit

Eulerian path / circuit 適合處理「每條邊都要剛好使用一次」的建構問題。題目不一定會直接說這是 Eulerian path；有時會包成排列、字串或密碼建構，例如要求所有長度為 n 的字串都在答案中出現一次。

實作時常用 Hierholzer algorithm：DFS 時先一路走尚未使用的邊，等目前節點已經沒有可走的邊，再把節點或邊的資訊加入答案。這個「遞迴回來後才加入答案」的 postorder traversal，是這類模板最重要的部分。

時間複雜度

  • Hierholzer algorithm：O(V + E)
  • Cracking the Safe：O(k^n)

Postorder Traversal 模板

C++
#include <bits/stdc++.h>
using namespace std;

vector<int> euler_traversal(vector<vector<int>>& adj, int start) {
    vector<int> path;

    auto dfs = [&](auto&& dfs, int cur) -> void {
        while (!adj[cur].empty()) {
            int next = adj[cur].back();
            adj[cur].pop_back();
            dfs(dfs, next);
        }

        path.push_back(cur);
    };

    dfs(dfs, start);
    reverse(path.begin(), path.end());

    return path;
}

若答案要記錄的是邊上的 label，而不是節點，則把 push_back 放在遞迴回來後：

C++
auto dfs = [&](auto&& dfs, int cur) -> void {
    for (int x = 0; x < k; ++x) {
        int edge = cur * k + x;

        if (used.count(edge)) continue;

        used.insert(edge);
        dfs(dfs, edge % mod);
        ans.push_back('0' + x);
    }
};

參考題型

  • LeetCode - Cracking the Safe：所有長度為 n 的密碼都要在答案中出現一次，可以把問題視為 de Bruijn graph 上的 Eulerian circuit。節點代表長度 n - 1 的 suffix，邊代表長度 n 的密碼。
C++
class Solution {
public:
    string crackSafe(int n, int k) {
        int mod = 1;
        for (int i = 0; i < n - 1; ++i) {
            mod *= k;
        }

        unordered_set<int> used;
        string ans;

        auto dfs = [&](auto&& dfs, int cur) -> void {
            for (int x = 0; x < k; ++x) {
                int edge = cur * k + x;

                if (used.count(edge)) continue;

                used.insert(edge);
                dfs(dfs, edge % mod);
                ans.push_back('0' + x);
            }
        };

        dfs(dfs, 0);
        ans += string(n - 1, '0');

        return ans;
    }
};