[hdu1269]城堡迷宫<tarjan强连通分量>

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1269

tarjan算法是oi里很常用的一个算法，在理解方面需要多下一些功夫，如果不行直接记模板也行，因为tarjan主要是细节不好理解。。。

我目前就是记得模板

然后这道题是个tarjan的裸题，就是把tarjan的模板打出来就可以A了

虽然我还是WA了很多次，最后总结原因发现是因为多组输入的原因，多组输入的时候n和m可能会单独存在0的情况（不同时为0），而我的初始程序就是只要有零就跳出，然后成功WA了多次（这是何等的窝草啊）

所以这题其实就是找下强联通个数，如果是一个就可以输出yes，否则输出no

当然你也可以主动去优化，优化方式就是当出现第一个强联通时不包括所有点就可以输出no然后exit(0)了

虽然优不优化这题都可以顺利通过

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<cstdlib>

 #define maxn 100005

 using namespace std;

 struct edge{

     int u,v,nxt;

 }e[maxn];

 int n,m,ans,head[maxn],dfn[maxn],low[maxn],belong[maxn];

 int read(){

     int xx=,ff=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')ff=-;ch=getchar();}

     while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}

     return xx*ff;

 }

 int tot;

 void adde(int u,int v){

     e[tot]=(edge){u,v,head[u]};

     head[u]=tot++;

 }

 stack<int>s;

 int num;

 void tarjan(int x){

     num++;

     dfn[x]=num;low[x]=num;

     s.push(x);

     for(int i=head[x];i!=-;i=e[i].nxt){

         int v=e[i].v;

         if(dfn[v]==){

             tarjan(v);

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

         }else{

             if(!belong[v]){low[x]=min(low[x],dfn[v]);}

         }

     }

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

         ans++;

         int u=s.top();

         while(u!=x){

             belong[u]=ans;

             s.pop();

             u=s.top();

         }belong[u]=ans;s.pop();

     }

 }

 int main(){

     while(){

         n=read();m=read();

         if(n==&&m==)return ;

         tot=;num=;ans=;

         while(!s.empty())s.pop();

         memset(dfn,,sizeof(dfn));

         memset(belong,,sizeof(belong));

         memset(low,,sizeof(low));

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

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

             int u,v;

             u=read();v=read();

             adde(u,v);

         }

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

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

         }

         if(ans==)printf("Yes\n");

         else printf("No\n");

     }

 }

【总结】

tarjan的理解比较难的地方就是他的low数组和low数组的值的变化，建议多结合图例去理解