首页 > 代码库 > Light OJ 1026 - Critical Links (图论-求割边, 桥)

Light OJ 1026 - Critical Links (图论-求割边, 桥)

题目大意:双向联通图, 现在求减少任意一边使图的联通性改变,按照起点从小到大列出所有这样的边

解题思路:双向边模版题 tarjan算法

代码如下:

技术分享
#include<bits/stdc++.h>using namespace std;const int N = 100003;vector<int>vec[N];pair<int, int>edge[N];int dfn[N], low[N];int res, ans;void tarjan(int u, int f){    dfn[u] = low[u] = res ++;    for(int i = 0; i < vec[u].size(); ++ i)    {        int v = vec[u][i];        if(dfn[v] == -1)        {            tarjan(v, u);            low[u] = min(low[u], low[v]);        }        else if(f != v)            low[u] = min(low[u], dfn[v]);        if(dfn[u] < low[v])        {            if(u > v)                edge[ans ++] = make_pair(v, u);            else                edge[ans ++] = make_pair(u, v);        }    }}void solve(int cases){    for(int i = 0; i < N; ++ i)        vec[i].clear();    int n;    scanf("%d", &n);    for(int i = 0; i < n; ++ i)    {        int a, b, c;        scanf("%d (%d)", &a, &b);        for(int j = 1; j <= b; ++ j)        {            scanf("%d", &c);            vec[a].push_back(c);        }    }    memset(dfn, -1, sizeof(dfn));    memset(low, -1, sizeof(low));    ans = res = 0;    for(int i = 0; i < n; ++ i)    {        if(dfn[i] == -1)            tarjan(i, -1);    }    sort(edge, edge+ans);    printf("Case %d:\n", cases);    printf("%d critical links\n", ans);    for(int i=0; i<ans; ++ i)        printf("%d - %d\n", edge[i].first, edge[i].second);}int main(){    int T;    scanf("%d", &T);    for(int i = 1; i <= T; ++ i)        solve(i);    return 0;}
View Code

 

Light OJ 1026 - Critical Links (图论-求割边, 桥)