Tarjan模板——求强接通分量

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\n",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\n",-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("\n");
115     return 0;
116 }

Tarjan模板——求强接通分量

相关推荐