tarjan-寻找图中有多少个强连通分量

tarjan寻找图中有多少个强连通分量

hdu 1269 迷宫城堡
判断图否是属于一个强连通分量

#include<bits/stdc++.h>
#define M 100100
using namespace std;
struct node
{
      int v;
      int next;
}edge[M];
int n,m,head[M];
int vis[M],low[M],dfn[M],cnt,tot;
int sig;
stack <int>s;
void add(int x,int y)
{
      edge[++cnt].next=head[x];
      edge[cnt].v=y;
      head[x]=cnt;
      return ;
}
void tarjan(int x)
{
      dfn[x]=low[x]=++tot;
      s.push(x);
      vis[x]=1;
      for(int i=head[x];i!=-1;i=edge[i].next)
      {
            if(!dfn[edge[i].v])
            {
                  tarjan(edge[i].v);
                  low[x]=min(low[x],low[edge[i].v]);
            }
            else if(vis[edge[i].v])
            {
                  low[x]=min(low[x],dfn[edge[i].v]);
            }
      }
      if(low[x]==dfn[x])
      {
            sig++;
            int k;
            do
            {
                  k=s.top( );
                  vis[k]=0;
                  s.pop();
            }while(x!=k);
      }
      return ;
}
int main( )
{
      int x,y;
      while(~scanf("%d%d",&n,&m)&&(m+n))
      {
            memset(head,-1,sizeof(head));
            memset(vis,0,sizeof(vis));
            memset(dfn,0,sizeof(dfn));
            memset(low,0,sizeof(low));
            cnt=tot=sig=0;
            for(int i=1;i<=m;i++)
            {
                  cin>>x>>y;
                  add(x,y);
            }
            for(int i=1;i<=n;i++)
            {
                  if(!dfn[i])
                  {
                        tarjan(i);
                  }
            }
            if(sig==1)
            {
                  cout<<"Yes"<<endl;
            }
            else
            {
                  cout<<"No"<<endl;
            }
      }
      return 0;
}