Tarjan模板——求强连通分量

Tarjan求强连通分量的流程在这个博客讲的很清楚，再加上我也没理解透，这里就不写了。

缩点:将同一个连通块内的点视为同一个点。

扔一道模板题：codeVS2822爱在心中

第一问很显然就是求点数大于一的连通块的个数，跑一次tarjan；

第二问脑补一下发现，缩点后，若图中有且仅有一个点出度为0且为爱心天使，则该点为所求的特殊爱心天使；

因为当缩点之后，图中不存在环，若有且仅有一个爱心天使出度为0，那么其他点一定有通向该爱心天使的路径。

若有两个点出度为0，那么他们彼此不被对方所爱。

若没有点出度为0，则图中存在环，矛盾。

看起来似乎没什么问题，但是写出来第五个点挂掉了，代码查不出错，若有人看到这篇博客，希望在下方指出错误，谢谢。

  1 #include<cstdio>
  2 #include<stack>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<iostream>
  7 using namespace std;
  8 
  9 struct edge{
 10     int to,next;
 11 };
 12 
 13 int a[5000][5000],dfn[10000],low[10000],head[10000],i,j,n,m,x,y,tag,ans[10000];
 14 int ans1=0,head2[10000],out[10000];
 15 bool visited[10000],b[10000],lowb[10000];
 16 edge e[10000],e2[10000];
 17 stack<int> s;
 18 
 19 void tarjan(int k){
 20     int i,v;
 21     dfn[k]=low[k]=++tag;
 22     b[k]=true;
 23     s.push(k);
 24     for(i=head[k];i!=-1;i=e[i].next){
 25         v=e[i].to;
 26         if(!dfn[v]){
 27             tarjan(v);
 28             low[k]=min(low[k],low[v]);
 29         }else
 30         if(b[v])
 31             low[k]=min(low[k],dfn[v]);
 32     }
 33     int tmp=0;
 34     if(dfn[k]==low[k]){
 35         //++ans1;
 36         do{
 37             v=s.top();
 38             s.pop();
 39             b[v]=false;
 40             tmp++;
 41         }while(v!=k);
 42         if(tmp>=2)++ans1;
 43     }
 44 }
 45 
 46 int ne=0;
 47 void add(int a,int b){
 48     e[++ne].to=b; e[ne].next=head[a]; head[a]=ne;
 49 }
 50 
 51 void add2(int a,int b){
 52     e2[++ne].to=b; e2[ne].next=head2[a]; head2[a]=ne;
 53 }
 54 
 55 int main(){
 56     memset(head,-1,sizeof(head));
 57     memset(head2,-1,sizeof(head2));
 58     scanf("%d%d",&n,&m);
 59     for(i=1;i<=m;i++){
 60         scanf("%d%d",&x,&y);
 61         add(x,y);
 62     }
 63     tag=0;
 64     memset(dfn,0,sizeof(dfn));
 65     for(i=1;i<=n;i++){
 66         if(!dfn[i])tarjan(i);
 67     }
 68     printf("%d
",ans1);
 69 
 70     ne=0;
 71     int n2=0;
 72 
 73     for(i=1;i<=n;i++){
 74         if(!lowb[low[i]]){
 75             n2=max(n2,low[i]);
 76             lowb[low[i]]=true;//记录缩点后图中节点的编号
 77         }
 78         a[low[i]][++a[low[i]][0]]=i;
 79         for(j=head[i];j!=-1;j=e[j].next){
 80             int v=e[j].to;
 81             if(low[i]!=low[v])
 82                 add2(low[i],low[v]);
 83         }
 84     //缩点:将low[]值相等的点看做一个点
 85     }
 86 
 87     for(i=1;i<=n2;i++){
 88         if(!lowb[i])continue;
 89         for(j=head2[i];j!=-1;j=e2[j].next)
 90             out[i]++;
 91     }
 92 
 93     int sum=0;
 94     for(i=1;i<=n2;i++){
 95         if(out[i]==0&&lowb[i]){
 96             sum++;
 97             j=i;
 98         };
 99     }
100 
101     if(sum!=1||a[j][0]<=1){
102         printf("%d
",-1);
103         return 0;
104     }
105 
106     for(i=1;i<=a[j][0];i++)
107         ans[i]=a[j][i];
108 
109     sort(ans+1,ans+1+a[j][0]);
110 
111     for(i=1;i<=a[j][0];i++)
112         printf("%d ",ans[i]);
113 
114     printf("
");
115     return 0;
116 }

16.11.18：换了一种写法A了，然而还是不知道原来的代码有什么问题；

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<stack>
 6 using namespace std;
 7 struct edge{int to,next;}e1[1000010],e2[1000010];
 8 int head1[600000],head2[600000],dfn[600000],low[600000],belong[600000],out[600000];
 9 bool instack[600000];
10 stack<int> s;
11 int dep,ne1,ne2,ans1,n,m,co;
12 void add1(int a,int b){
13     e1[++ne1].to=b;e1[ne1].next=head1[a];head1[a]=ne1;
14 }
15 void add2(int a,int b){
16     e2[++ne2].to=b;e2[ne2].next=head2[a];head2[a]=ne2;
17 }
18 void tarjan(int k){
19     dfn[k]=low[k]=++dep;
20     instack[k]=true;
21     s.push(k);
22     for(int i=head1[k];i!=-1;i=e1[i].next){
23         int v=e1[i].to;
24         if(!dfn[v]){
25             tarjan(v);
26             low[k]=min(low[k],low[v]);
27         }
28         else if(instack[v])
29             low[k]=min(low[k],dfn[v]);
30     }
31     int t;
32     if(low[k]==dfn[k]){
33         int tmp=0;
34         ++co;
35         do{
36             t=s.top();
37             s.pop();
38             instack[t]=false;
39             belong[t]=co;//染色缩点 
40             tmp++;
41         }while(t!=k);
42         if(tmp>1)++ans1;
43     }
44 }
45 
46 int main(){
47     memset(head1,-1,sizeof(head1));
48     memset(head2,-1,sizeof(head2));
49     int i,j,u,v;
50     scanf("%d%d",&n,&m);
51     for(i=1;i<=m;i++){
52         scanf("%d%d",&u,&v);
53         add1(u,v);
54     }
55     for(i=1;i<=n;i++){
56         if(!dfn[i])tarjan(i);
57     }
58     printf("%d
",ans1);
59     
60     int sum=0,ang=0;
61     for(i=1;i<=n;i++){
62         for(j=head1[i];j!=-1;j=e1[j].next){
63             int v=e1[j].to;
64             if(belong[v]!=belong[i]){
65                 out[belong[i]]++;//若邻接的两点颜色不同，则出度加一。 
66             }
67         }
68     }
69     for(i=1;i<=co;i++){
70         if(out[i]==0){
71             ang=i;
72             ++sum;
73         }
74     }
75     if(sum==1){
76         int sum2=0;
77         for(i=1;i<=n;i++){
78             if(belong[i]==ang)sum2++;
79         }
80         if(sum2>1){
81             for(i=1;i<=n;i++){
82                 if(belong[i]==ang)printf("%d ",i);
83             }
84             printf("
");
85         }else{printf("-1
");return 0;}
86         return 0;
87     }
88     printf("-1
");return 0;
89 }