問題定義

在無向圖中找出所有橋（割邊）：刪除後圖連通分量增加的邊。輸出橋的輸入序號。

Tarjan 算法核心原理

• DFS 時間戳：dfn[u] = 訪問順序，low[u] = 子樹能回溯到的最早祖先
• 橋判定條件：樹邊 (u,v) 滿足 low[v] > dfn[u] 則為橋
• 重邊處理：並行邊不構成橋，需標記邊 ID 去重

完整 C++ 實現

#include 
using namespace std;

const int MAXN = 20010;

struct Edge {
    int to, id, num;  // num: 0=正向, 1=反向（用於去重）
    Edge(int a, int b, int c) : to(a), id(b), num(c) {}
};

vector G[MAXN];
int dfn[MAXN], low[MAXN], ans[MAXN], vis[MAXN];
int n, m, dfs_clock, ans_cnt;

void dfs(int u, int parent_edge_id) {
    vis[u] = 1;
    dfn[u] = low[u] = ++dfs_clock;
    
    for (auto &e : G[u]) {
        if (e.num == 1 && e.id == parent_edge_id) continue;  // 跳過反向邊
        
        if (!vis[e.to]) {
            dfs(e.to, e.id);
            low[u] = min(low[u], low[e.to]);
            
            // 橋判定：low[v] > dfn[u] 且非重邊
            if (low[e.to] > dfn[u] && e.num == 0)
                ans[ans_cnt++] = e.id;
        } else {
            // 回邊：更新 low
            low[u] = min(low[u], dfn[e.to]);
        }
    }
}

int tarjan() {
    dfs_clock = ans_cnt = 0;
    memset(vis, 0, sizeof(vis));
    dfs(1, -1);  // 假設圖連通，從 1 開始
    return ans_cnt;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i=1; i<=n; i++) G[i].clear();
        
        for (int i=1; i<=m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            G[a].push_back(Edge(b, i, 0));  // 正向邊
            G[b].push_back(Edge(a, i, 1));  // 反向邊（同 id，num=1）
        }
        
        int cnt = tarjan();
        sort(ans, ans + cnt);
        for (int i=0; i