kuangbin专题专题九连通图 Critical Links UVA - 796

佚名 4年前 (2020-01-14) 算法 1284人围观抢沙发百度已收录

题目：裸的求桥，按第一个元素升序输出即可。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 #define pb push_back
 7 #define fi first
 8 #define se second
 9 
10 const int N = (int)1e3+10;
11 int n,tot,tim;
12 int head[N],dfn[N],low[N];
13 struct node{
14     int to;
15     int nxt;
16 }e[N*N];
17 vector<pair<int,int> > cut;
18 
19 void init(){
20     for(int i = 0; i <= n; ++i){
21         head[i] = -1;
22         dfn[i] = 0;
23     }
24     tim = tot = 0;
25 }
26 
27 inline void add(int u,int v){
28     e[tot].to = v;
29     e[tot].nxt = head[u];
30     head[u] = tot++;
31 }
32 
33 void tarjan(int now,int pre){
34     dfn[now] = low[now] = ++tim;
35     int to;
36     for(int o = head[now]; ~o; o = e[o].nxt){
37         to = e[o].to;
38         if(to == pre) continue;//双向边的判断
39         if(!dfn[to]){
40             tarjan(to,now);
41             low[now] = min(low[now],low[to]);
42             //桥的条件
43             if(dfn[now] < low[to]) cut.pb(make_pair(min(now,to),max(now,to)));
44         }
45         else if(low[now] > dfn[to]) low[now] = dfn[to];
46     }
47 }
48 
49 void _ans(){
50 
51     int ans = cut.size();
52     sort(cut.begin(),cut.end());
53     printf("%d critical links\n",ans);
54     for(int i = 0; i < ans; ++i) printf("%d - %d\n",cut[i].fi,cut[i].se);
55     printf("\n");
56     cut.clear();
57 }
58 
59 int main(){
60 
61     int u,v,m;
62     while(~scanf("%d",&n)){
63         init();
64 
65         for(int i = 0; i < n; ++i){
66             scanf("%d (%d)",&u,&m);
67             for(int j = 0; j < m; ++j){
68                 scanf("%d",&v);
69                 add(u,v);
70             }
71         }
72 
73         for(int i = 0; i < n; ++i) if(!dfn[i]) tarjan(i,i);
74         _ans();
75     }
76 
77     return 0;
78 }