(UVA) 796 - Critical Links [割邊 bridge]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=737

裸割邊題，也是一樣用tarjan的low函數，不過這次需要考慮重邊 & 從父親來的節點XD。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e5+6; //assume, not given in the input

int low[MAX_N];
int depth[MAX_N];
bool visit[MAX_N];
vector<int> edg[MAX_N];
pii ans[MAX_N];
int ans_no;
set<pii> path;
set<pii> repeat;

void dfs(int id,int cur_depth,int parent) {
    visit[id]=true;
    low[id]=cur_depth;
    depth[id]=cur_depth;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==true) {
            if (depth[tmp] < low[id] && tmp!=parent) {
                low[id] = depth[tmp];
            }
            else if (depth[tmp]<low[id] && repeat.find(make_pair(tmp,id))!=repeat.end()) {
                low[id] = depth[tmp];
            }
        }
        else {
            dfs(tmp,cur_depth+1,id);
            if (low[tmp] < low[id]) low[id]=low[tmp];
        }
    }
    if (id!=parent && low[id]>=cur_depth) {
        ans[ans_no++]=make_pair(min(parent,id),max(parent,id));
    }
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        for (int x=0;n>x;x++) {
            edg[x].clear();
            visit[x]=false;
            ans_no=0;
        }
        ans_no=0;
        for (int x=0;n>x;x++) {
            int i,j;
            scanf("%d (%d)",&i,&j);
            for (int y=0;j>y;y++) {
                int k;
                scanf("%d",&k);
                edg[i].push_back(k);
                edg[k].push_back(i);
            }
        }
        for (int x=0;n>x;x++) {
            if (visit[x]==false) dfs(x,1,x);
        }
        sort(ans,ans+ans_no);
        printf("%d critical links\n",ans_no);
        for (int x=0;ans_no>x;x++) {
            printf("%d - %d\n",ans[x].first,ans[x].second);
        }
        puts("");
    }
}