首页 > 代码库 > tarjan scc

tarjan scc

luogu1

luogu2

输出不同

1

#include<iostream>#include<stack>#include <cstring>using namespace std;int m,ans,bbk[205],bk,b[205],head[205],cnt,dfn[205],low[205],n;stack<int>zz;bool ru[205];struct aa{    int to,next;}e[40005];void add(int x, int y){    e[cnt].to = y;    e[cnt].next = head[x];    head[x] = cnt++;}/*void add(int from,int to){    e[++cnt]=(aa){to,head[from]};    head[from]=cnt;}*/void dfs(int k){    dfn[k]=low[k]= ++cnt;    b[k]=1;    zz.push(k);    int j;    for(int i=head[k];i!=-1;i=e[i].next){        j=e[i].to;        if(!dfn[j]){            dfs(j);            low[k]=min(low[k],low[j]);        }        else if(b[j]&&dfn[j]<low[k])low[k]=dfn[j];    }    if(dfn[k]==low[k]){        bk++;        do{            j=zz.top();            zz.pop();            b[j]=0;            bbk[j]=bk;        }while(j!=k);    }}int main(){    cin>>n;    memset(head, -1, sizeof(head));    for(int x,i=1;i<=n;i++){        cin>>x;        while(x){            add(i,x);            cin>>x;        }    }    cnt=0;    for(int i=1;i<=n;i++)      if(!dfn[i])        dfs(i);    for(int i=1;i<=n;i++)      for(int y,j=head[i];j!=-1;j=e[j].next){          y=e[j].to;          if(bbk[y]!=bbk[i])ru[bbk[y]]=1;      }    for(int i=1;i<=bk;i++)      if(!ru[i])        ans++;    cout<<ans;    return 0;}

2

#include<iostream>#include<stack>using namespace std;int m,ans,bbk[10000],bk,b[10005],head[10005],cnt,dfn[10005],low[10005],n;stack<int>zz;struct aa{    int to,next;}e[50002];void add(int from,int to){    e[++cnt]=(aa){to,head[from]};    head[from]=cnt;}void dfs(int k){    dfn[k]=low[k]= ++cnt;    b[k]=1;    zz.push(k);    int j;    for(int i=head[k];i;i=e[i].next){        j=e[i].to;        if(!dfn[j]){            dfs(j);            low[k]=min(low[k],low[j]);        }        else if(b[j]&&dfn[j]<low[k])low[k]=dfn[j];    }    if(dfn[k]==low[k]){        bk++;        do{            j=zz.top();            zz.pop();            b[j]=0;            bbk[bk]++;        }while(j!=k);    }}int main(){    cin>>n>>m;    for(int x,y,i=1;i<=m;i++){        cin>>x>>y;        add(x,y);    }    cnt=0;    for(int i=1;i<=n;i++)      if(!dfn[i])        dfs(i);    for(int i=1;i<=bk;i++)      if(bbk[i]>1)        ans++;    cout<<ans;    return 0;}

 

tarjan scc