有向图强连通分量

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<stack>
 6 using namespace std;
 7 struct edge{
 8     int v,next;
 9 }a[100001];
10 stack<int>s;
11 int n,m,u,v,sum=0,tt=-1,ans=0,h[100001],anss[100001],num[100001],nums[100001],tot=0,tim=0,dfn[100001],low[100001],head[100001];
12 bool used[100001],isin[100001];
13 void tarjan(int u){
14     int v;
15     used[u]=isin[u]=true;
16     low[u]=dfn[u]=++tim;
17     s.push(u);
18     for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
19         v=a[tmp].v;
20         if(!used[v]){
21             tarjan(v);
22             low[u]=min(low[u],low[v]);
23         }else{
24             if(isin[v])low[u]=min(low[u],dfn[v]);
25         }
26     }
27     if(low[u]==dfn[u]){
28         v=-1;
29         sum++;
30         while(v!=u){
31             v=s.top();
32             s.pop();
33             isin[v]=0;
34             num[v]=sum;
35             nums[sum]++;
36         }
37     }
38 }
39 void add(int u,int v){
40     a[++tot].v=v;
41     a[tot].next=head[u];
42     head[u]=tot;
43 }
44 int main(){
45     memset(used,0,sizeof(used));
46     memset(head,-1,sizeof(head));
47     memset(h,-1,sizeof(h));
48     scanf("%d%d",&n,&m);
49     for(int i=1;i<=m;i++){
50         scanf("%d%d",&u,&v);
51         add(u,v);
52     }
53     for(int i=1;i<=n;i++){
54         if(!used[i])tarjan(i);
55     }
56     tot=0;
57     for(int i=1;i<=n;i++){
58         for(int tmp=head[i];tmp!=-1;tmp=a[tmp].next){
59             if(num[i]!=num[a[tmp].v]){
60                 h[num[i]]=++tot;
61             }
62         }
63     }
64     for(int i=1;i<=sum;i++){
65         if(nums[i]>1)ans++;
66     }
67     printf("%d
",ans);
68     for(int i=1;i<=sum;i++){
69         if(h[i]==-1){
70              if(tt!=-1||nums[i]==1){
71                 tt=-1;
72                 break;
73              }else tt=i;
74         }
75     }
76     if(tt==-1)printf("-1");
77     else for(int i=1;i<=n;i++){
78         if(num[i]==tt)printf("%d ",i);
79     }
80     return 0;
81 }

无向图割点

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cmath>
  5 using namespace std;
  6 struct edge{
  7     int v,next;
  8 }a[100001];
  9 int t=0,n,s,ss,u,v,tim=0,sum=0,tot=0,head[100001],dfn[100001],low[100001];
 10 bool f=false,used[100001],ff[100001];
 11 void add(int u,int v){
 12     a[++tot].v=v;
 13     a[tot].next=head[u];
 14     head[u]=tot;
 15 }
 16 void tarjan(int u,int fa){
 17     int v;
 18     dfn[u]=low[u]=++tim;
 19     for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
 20         v=a[tmp].v;
 21         if(!low[v]){
 22             tarjan(v,u);
 23             if(u==1)sum++;
 24             low[u]=min(low[u],low[v]);
 25             if(u!=1&&dfn[u]<=low[v]){
 26                 ff[u]=true;
 27             }
 28         }else if(v!=fa){
 29             low[u]=min(low[u],dfn[v]);
 30         }
 31     }
 32 }
 33 void dfs(int u){
 34     int v;
 35     used[u]=true;
 36     for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
 37         v=a[tmp].v;
 38         if(!used[v])dfs(v);
 39     }
 40 }
 41 int main(){
 42     while(scanf("%d",&s)&&s){
 43         printf("Network #%d
",++t);
 44         memset(head,-1,sizeof(head));
 45         memset(ff,0,sizeof(ff));
 46         memset(dfn,0,sizeof(dfn));
 47         memset(low,0,sizeof(low));
 48         tot=n=sum=tim=0;
 49         f=false;
 50         scanf("%d",&ss);
 51         add(s,ss);
 52         add(ss,s);
 53         n=max(n,max(s,ss));
 54         scanf("%d",&s);
 55         while(s){
 56             scanf("%d",&ss);
 57             add(s,ss);
 58             add(ss,s);
 59             n=max(n,max(s,ss));
 60             scanf("%d",&s);
 61         }
 62         tarjan(1,-1);
 63         if(sum>1)ff[1]=true;
 64         for(int i=1;i<=n;i++){
 65             if(ff[i]){
 66                 memset(used,0,sizeof(used));
 67                 f=used[i]=true;
 68                 sum=0;
 69                 for(int j=1;j<=n;j++){
 70                     if(!used[j]){
 71                         sum++;
 72                         dfs(j);
 73                     }
 74                 }
 75                 printf("  SPF node %d leaves %d subnets
",i,sum);  
 76             }
 77         }
 78         if(!f){
 79             printf("  No SPF nodes
");
 80         }
 81         printf("
");
 82     }
 83     return 0;
 84 }
 85 /*
 86 1 2
 87 5 4
 88 3 1
 89 3 2
 90 3 4
 91 3 5
 92 0
 93 
 94 1 2
 95 2 3
 96 3 4
 97 4 5
 98 5 1
 99 0
100 
101 1 2
102 2 3
103 3 4
104 4 6
105 6 3
106 2 5
107 5 1
108 0
109 
110 0
111 --------
112 Network #1
113   SPF node 3 leaves 2 subnets
114 
115 Network #2
116   No SPF nodes
117 
118 Network #3
119   SPF node 2 leaves 2 subnets
120   SPF node 3 leaves 2 subnets
121 */

无向图点双连通分量

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<cmath>
 6 #include<stack>
 7 using namespace std;
 8 struct edge{
 9     int v,next;
10 }a[200001];
11 struct edge1{
12     int u,v;
13 };
14 int n,m,u,v,tot=0,tim=0,bcctot=0,bccnum[100001],head[100001],dfn[100001],low[100001],iscut[100001];
15 vector<int>ans[100001];
16 stack<edge1>s;
17 void add(int u,int v){
18     a[++tot].v=v;
19     a[tot].next=head[u];
20     head[u]=tot;
21 }
22 void tarjan(int u,int fa){
23     edge1 t;
24     int v,son;
25     dfn[u]=low[u]=++tim;
26     for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
27         v=a[tmp].v;
28         if(v==fa)continue;
29         t.u=u;
30         t.v=v;
31         if(!dfn[v]){
32             s.push(t);
33             son++;
34             tarjan(v,u);
35             low[u]=min(low[u],low[v]);
36             if(low[v]>=dfn[u]){
37                 iscut[u]=true;
38                 ans[++bcctot].clear();
39                 while(true){
40                     edge1 tt=s.top();
41                     s.pop();
42                     if(bccnum[tt.u]!=bcctot){
43                         ans[bcctot].push_back(tt.u);
44                         bccnum[tt.u]=bcctot;
45                     }
46                     if(bccnum[tt.v]!=bcctot){
47                         ans[bcctot].push_back(tt.v);
48                         bccnum[tt.v]=bcctot;
49                     }
50                     if(tt.u==u&&tt.v==v)break;
51                 }
52             }
53         }else if(dfn[v]<low[u]){
54             s.push(t);
55             low[u]=min(low[u],dfn[v]);
56         }
57     }
58     if(fa<0&&son==1)iscut[u]=false;
59 }
60 int main(){
61     memset(iscut,0,sizeof(iscut));
62     memset(head,-1,sizeof(head));
63     memset(low,0,sizeof(low));
64     memset(bccnum,0,sizeof(bccnum));
65     scanf("%d%d",&n,&m);
66     for(int i=1;i<=m;i++){
67         scanf("%d%d",&u,&v);
68         add(u,v);
69         add(v,u);
70     }
71     tarjan(1,-1);
72     for(int i=1;i<=bcctot;i++){
73         printf("%d:",i);
74         for(int j=0;j<ans[i].size();j++){
75             printf("%d ",ans[i][j]);
76         }
77         printf("
");
78     }
79     return 0;
80 }
81 /*
82 6 7 
83 1 2 
84 2 3 
85 1 3 
86 3 4 
87 4 5 
88 3 5 
89 5 6 
90 --------
91 1:5 6
92 2:4 3 5
93 3:2 1 3
94 */

无向图求桥

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 using namespace std;
 6 struct edge{
 7     int u,v,next;
 8 }a[100001];
 9 int n,m,u,v,tot=0,tim=0,head[100001],dfn[100001],low[100001],ansu[100001],ansv[100001];
10 void add(int u,int v){
11     a[++tot].u=u;
12     a[tot].v=v;
13     a[tot].next=head[u];
14     head[u]=tot;
15 }
16 void tarjan(int u,int fa){
17     int v;
18     dfn[u]=low[u]=++tim;
19     for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
20         v=a[tmp].v;
21         if(dfn[v]==0){
22             tarjan(v,u);
23             low[u]=min(low[u],low[v]);
24             if(low[v]>dfn[u]){
25                 ansu[++ansu[0]]=u;
26                 ansv[++ansv[0]]=v;
27             }
28         }else{
29             if(dfn[v]<dfn[u]&&v!=fa){
30                 low[u]=min(low[u],dfn[v]);
31             }
32         }
33     }
34 }
35 int main(){
36     memset(head,-1,sizeof(head));
37     memset(dfn,0,sizeof(dfn));
38     memset(low,0,sizeof(low));
39     ansu[0]=0;
40     ansv[0]=0;
41     scanf("%d%d",&n,&m);
42     for(int i=1;i<=m;i++){
43         scanf("%d%d",&u,&v);
44         add(u,v);
45         add(v,u);
46     }
47     tarjan(1,-1);
48     printf("--------
");
49     for(int i=1;i<=ansv[0];i++){
50         printf("%d %d
",ansu[i],ansv[i]);
51     }
52     return 0;
53 }
54 /*
55 6 7
56 1 2
57 2 3
58 1 3
59 3 4
60 4 5
61 5 6
62 6 4
63 --------
64 3 4
65 */

无向图边双连通分量

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<cmath>
 6 using namespace std;
 7 struct edge{
 8     int v,next;
 9 }a[100001];
10 int n,m,u,v,tot=0,tim=0,num=0,head[100001],dfn[100001],low[100001],bl[100001];
11 bool used[100001],bri[100001];
12 vector<int>g[100001];
13 void add(int u,int v){
14     a[++tot].v=v;
15     a[tot].next=head[u];
16     head[u]=tot;
17 }
18 void tarjan(int u,int fa){
19     int v;
20     dfn[u]=low[u]=++tim;
21     for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
22         v=a[tmp].v;
23         if(dfn[v]==0){
24             tarjan(v,u);
25             low[u]=min(low[u],low[v]);
26             if(low[v]>dfn[u]){
27                 bri[tmp]=true;
28                 bri[tmp^1]=true;
29             }
30         }else{
31             if(dfn[v]<dfn[u]&&v!=fa){
32                 low[u]=min(low[u],dfn[v]);
33             }
34         }
35     }
36 }
37 void dfs(int u){
38     used[u]=true;
39     bl[u]=num;
40     g[num].push_back(u);
41     for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
42         int v=a[tmp].v;
43         if(bri[tmp])continue;
44         if(!used[v])dfs(v);
45     }
46 }
47 int main(){
48     memset(head,-1,sizeof(head));
49     memset(dfn,0,sizeof(dfn));
50     memset(low,0,sizeof(low));
51     memset(used,0,sizeof(used));
52     memset(bri,0,sizeof(bri));
53     memset(bl,0,sizeof(bl));
54     scanf("%d%d",&n,&m);
55     for(int i=1;i<=m;i++){
56         scanf("%d%d",&u,&v);
57         add(u,v);
58         add(v,u);
59     }
60     for(int i=1;i<=n;i++){
61         if(!dfn[i])tarjan(i,-1);
62     }
63     for(int i=1;i<=n;i++){
64         if(!used[i]){
65             num++;
66             dfs(i);
67         }
68     }
69     for(int i=1;i<=num;i++){
70         printf("%d: ",i);
71         for(int j=0;j<g[i].size();j++)printf("%d ",g[i][j]);
72         printf("
");
73     }
74     return 0;
75 }