HDU

Proving Equivalences

HDU - 2767

UVALive - 4287

Equivalent Sets

HDU - 3836

题意：有向图，问还需要加几条边才变成强连通。

求出各强连通分量，缩成一个点，新图是DAG

求出新图各点还需要的入度和出度（因为只有每个点的入度和出度至少为1才是强连通）

然后求出所需入度为1的连通分量数a和出度为1的连通分量数b，答案为max（a,b)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxv=20010;
 4 const int maxe=50010;
 5 
 6 int n,m;
 7 
 8 struct Edge{
 9     int u,v,nex;
10 }e[maxe<<1];
11 int head[maxv];
12 int cnt=0;
13 void init(){
14     memset(head,-1,sizeof(head));
15     cnt=0;
16 }
17 void add(int u,int v){
18     e[cnt].u=u;
19     e[cnt].v=v;
20     e[cnt].nex=head[u];
21     head[u]=cnt++;
22 }
23 
24 int pre[maxv],sccno[maxv],lowlink[maxv],dfsk,scc_cnt;
25 stack<int> s;
26 
27 void dfs(int u){
28     pre[u]=lowlink[u]=++dfsk;
29     s.push(u);
30     for(int i=head[u];i!=-1;i=e[i].nex){
31         int v=e[i].v;
32         if(!pre[v]){
33             dfs(v);
34             lowlink[u]=min(lowlink[u],lowlink[v]);
35         }
36         else if(!sccno[v])
37             lowlink[u]=min(lowlink[u],lowlink[v]);
38     }
39     if(lowlink[u]==pre[u]){
40         scc_cnt++;
41         for(;;){
42             int x=s.top();
43             s.pop();
44             sccno[x]=scc_cnt;
45             if(x==u) break;
46         }
47     }
48 }
49 
50 void find_scc(int n){
51     dfsk=scc_cnt=0;
52     memset(sccno,0,sizeof(sccno));
53     memset(pre,0,sizeof(pre));
54     for(int i=0;i<n;i++) if(!pre[i]) dfs(i);
55 }
56 int in0[maxv],out0[maxv];
57 
58 int main(){
59     int t;
60     scanf("%d",&t);
61     while(t--){
62         init();
63         scanf("%d%d",&n,&m);
64         for(int i=0;i<m;i++){
65             int u,v;
66             scanf("%d%d",&u,&v);
67             u--;v--;
68             add(u,v);
69         }
70         find_scc(n);
71 
72         for(int i=1;i<=scc_cnt;i++) in0[i]=out0[i]=1;
73         for(int u=0;u<n;u++){
74             for(int i=head[u];i!=-1;i=e[i].nex){
75                 int v=e[i].v;
76                 if(sccno[v]!=sccno[u]) in0[sccno[v]]=out0[sccno[u]]=0;
77             }
78         }
79         int a=0,b=0;
80         for(int i=1;i<=scc_cnt;i++){
81             if(in0[i]) a++;
82             if(out0[i]) b++;
83         }
84         int ans=max(a,b);
85         if(scc_cnt==1) ans=0;
86         printf("%d
",ans);
87     }
88     return 0;
89 }

View Code