题目大意：

给你一个迷宫 给你结点个数和一定数目的单向边

问你迷宫是否强连通

做这道题这是为了练习一下Tarjan算法

关于这个算法网上很多而已版本 大多都一样 我就不多说了

详解见代码注释

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=10005;struct node{ struct tt *next;}mem[N];struct tt{ int b; struct tt *next;};int low[N];//逆向边可达最前父结点int dfn[N];//深度bool in[N];//是否在栈里面bool visited[N];//是否访问过stack
           
            str;void build(int a,int b)//建邻接表{ struct tt *t=new tt; t->b=b; t->next=mem[a].next; mem[a].next=t;}int deep,num;//深度 和 访问结点的个数bool Tarjan(int x){ ++deep; low[x]=dfn[x]=deep;//初始化 str.push(x); in[x]=true; visited[x]=true;++num; struct tt *t=mem[x].next; while(t!=NULL) { if(visited[t->b]==false)//如果没访问过 则深搜 { if(Tarjan(t->b)==false)//如果已经不合题意 则可停止 return false; low[x]=min(low[x],low[t->b]); } else if(in[t->b]==true)//如果在栈里面 { low[x]=min(low[x],dfn[t->b]); } t=t->next; } /* while(t!=NULL)//本来想看这样对不对 因为网上的代码都是上面的 我感觉下面的也对 {//提交也对了 也可能是只适合本题 亦可能这个本身也对 以后还须继续证明 if(visited[t->b]==false) { if(Tarjan(t->b)==false) return false; } low[x]=min(low[x],low[t->b]); t=t->next; } */ if(dfn[x]==low[x]) { if(x!=1)//从 1 开始搜的 唯一的连同分支根结点是 1 否则就错 return false; return true; } return true;}void clear(int n)//每次要对邻接表表头进行处理{ for(int i=1;i<=n;++i) mem[i].next=NULL;}int main(){ int n,m; while(scanf("%d %d",&n,&m)!=EOF) { deep=0; num=0; if(n==0&&m==0) break; while(m--) { int a,b; scanf("%d %d",&a,&b); build(a,b); } memset(in,false,sizeof(in)); memset(visited,false,sizeof(visited)); if(Tarjan(1)&&num==n)//注意要满足 每个点都被访问过 printf("Yes\n"); else printf("No\n"); clear(n); } return 0;}