Tarjan模板——求强连通分量

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

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

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

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

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

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

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

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

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

 #include<cstdio>

 #include<stack>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 struct edge{

     int to,next;

 };

 int a[][],dfn[],low[],head[],i,j,n,m,x,y,tag,ans[];

 int ans1=,head2[],out[];

 bool visited[],b[],lowb[];

 edge e[],e2[];

 stack<int> s;

 void tarjan(int k){

     int i,v;

     dfn[k]=low[k]=++tag;

     b[k]=true;

     s.push(k);

     for(i=head[k];i!=-;i=e[i].next){

         v=e[i].to;

         if(!dfn[v]){

             tarjan(v);

             low[k]=min(low[k],low[v]);

         }else

         if(b[v])

             low[k]=min(low[k],dfn[v]);

     }

     int tmp=;

     if(dfn[k]==low[k]){

         //++ans1;

         do{

             v=s.top();

             s.pop();

             b[v]=false;

             tmp++;

         }while(v!=k);

         if(tmp>=)++ans1;

     }

 }

 int ne=;

 void add(int a,int b){

     e[++ne].to=b; e[ne].next=head[a]; head[a]=ne;

 }

 void add2(int a,int b){

     e2[++ne].to=b; e2[ne].next=head2[a]; head2[a]=ne;

 }

 int main(){

     memset(head,-,sizeof(head));

     memset(head2,-,sizeof(head2));

     scanf("%d%d",&n,&m);

     for(i=;i<=m;i++){

         scanf("%d%d",&x,&y);

         add(x,y);

     }

     tag=;

     memset(dfn,,sizeof(dfn));

     for(i=;i<=n;i++){

         if(!dfn[i])tarjan(i);

     }

     printf("%d\n",ans1);

     ne=;

     int n2=;

     for(i=;i<=n;i++){

         if(!lowb[low[i]]){

             n2=max(n2,low[i]);

             lowb[low[i]]=true;//记录缩点后图中节点的编号

         }

         a[low[i]][++a[low[i]][]]=i;

         for(j=head[i];j!=-;j=e[j].next){

             int v=e[j].to;

             if(low[i]!=low[v])

                 add2(low[i],low[v]);

         }

     //缩点:将low[]值相等的点看做一个点

     }

     for(i=;i<=n2;i++){

         if(!lowb[i])continue;

         for(j=head2[i];j!=-;j=e2[j].next)

             out[i]++;

     }

     int sum=;

     for(i=;i<=n2;i++){

         if(out[i]==&&lowb[i]){

             sum++;

             j=i;

         };

     }

     if(sum!=||a[j][]<=){

         printf("%d\n",-);

         return ;

     }

     for(i=;i<=a[j][];i++)

         ans[i]=a[j][i];

     sort(ans+,ans++a[j][]);

     for(i=;i<=a[j][];i++)

         printf("%d ",ans[i]);

     printf("\n");

     return ;

 }

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

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<stack>

 using namespace std;

 struct edge{int to,next;}e1[],e2[];

 int head1[],head2[],dfn[],low[],belong[],out[];

 bool instack[];

 stack<int> s;

 int dep,ne1,ne2,ans1,n,m,co;

 void add1(int a,int b){

     e1[++ne1].to=b;e1[ne1].next=head1[a];head1[a]=ne1;

 }

 void add2(int a,int b){

     e2[++ne2].to=b;e2[ne2].next=head2[a];head2[a]=ne2;

 }

 void tarjan(int k){

     dfn[k]=low[k]=++dep;

     instack[k]=true;

     s.push(k);

     for(int i=head1[k];i!=-;i=e1[i].next){

         int v=e1[i].to;

         if(!dfn[v]){

             tarjan(v);

             low[k]=min(low[k],low[v]);

         }

         else if(instack[v])

             low[k]=min(low[k],dfn[v]);

     }

     int t;

     if(low[k]==dfn[k]){

         int tmp=;

         ++co;

         do{

             t=s.top();

             s.pop();

             instack[t]=false;

             belong[t]=co;//染色缩点

             tmp++;

         }while(t!=k);

         if(tmp>)++ans1;

     }

 }

 int main(){

     memset(head1,-,sizeof(head1));

     memset(head2,-,sizeof(head2));

     int i,j,u,v;

     scanf("%d%d",&n,&m);

     for(i=;i<=m;i++){

         scanf("%d%d",&u,&v);

         add1(u,v);

     }

     for(i=;i<=n;i++){

         if(!dfn[i])tarjan(i);

     }

     printf("%d\n",ans1);

     int sum=,ang=;

     for(i=;i<=n;i++){

         for(j=head1[i];j!=-;j=e1[j].next){

             int v=e1[j].to;

             if(belong[v]!=belong[i]){

                 out[belong[i]]++;//若邻接的两点颜色不同，则出度加一。

             }

         }

     }

     for(i=;i<=co;i++){

         if(out[i]==){

             ang=i;

             ++sum;

         }

     }

     if(sum==){

         int sum2=;

         for(i=;i<=n;i++){

             if(belong[i]==ang)sum2++;

         }

         if(sum2>){

             for(i=;i<=n;i++){

                 if(belong[i]==ang)printf("%d ",i);

             }

             printf("\n");

         }else{printf("-1\n");return ;}

         return ;

     }

     printf("-1\n");return ;

 }

巴特西

Tarjan模板——求强连通分量

最新文章

热门文章