hdu1269迷宫城堡(判断有向图是否是一个强连通图)

  1
     /*
          题意： 给你一个图，求这个有向图示否是一个强连通图（每两个节点都是可以相互到达的）！
          思路1：按正向边dfs一遍，将经过的节点计数，如果记录的节点的个数小于n，那么就说明图按照正向边就不是连同的，所以就不是强连通图！
                然后按照反向边再进行另一个dfs，同样对经过的节点的个数进行计数，如果个数==n则说明正向遍历和反响遍历都是连通的！那么整个图就是强连通的图！

          思路2：直接套用tarjan算法，求出每一个节点所对应的缩点的值， 如果缩点的个数==1，那么证明就会只有一个强连通分量！也就是强连通图

          思路3：多次次调用tarjan算法，判断low[u]==pre[u]&&u==1, 如果不满足说明改图有多个缩点，那就不是强连通图!下图说明一下....         

     */
  //思路一：
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #define N 10005

 using namespace std;

 vector<int>uv[N];

 vector<int>vu[N];

 int vis[N];

 int cnt;

 int n, m;

 void dfs1(int u){

     vis[u]=1;

     ++cnt;

     int len=uv[u].size();

     for(int i=0; i<len; ++i){

         int v=uv[u][i];

         if(!vis[v])

            dfs1(v);

     }

 }

 void dfs2(int v){

     vis[v]=1;

     ++cnt;

     int len=vu[v].size();

     for(int i=0; i<len; ++i){

         int u=vu[v][i];

         if(!vis[u])

            dfs2(u);

     }

 }

 int main(){

    while( scanf("%d%d", &n, &m) && (n||m) ){

        memset(vis, 0, sizeof(vis));

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

            uv[i].clear();

            vu[i].clear();

        }

        while(m--){

            int u, v;

            scanf("%d%d", &u, &v);

            uv[u].push_back(v);

            vu[v].push_back(u);

        }

        cnt=0;

        dfs1(1);

        if(cnt==n){

           memset(vis, 0, sizeof(vis));

           cnt=0;

           dfs2(1);

           if(cnt!=n)

              printf("No\n");

           else printf("Yes\n");

        }

        else printf("No\n");

    }

    return 0;

 }

 //思路二：
 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<stack>

 #define N 10005

 using namespace std;

 vector<int>g[N];

 stack<int>s;

 int pre[N], low[N];

 int scc[N];

 int scc_cnt;

 int dfs_clock;

 void tarjans(int u){

     pre[u]=low[u]=++dfs_clock;

     s.push(u);

     int len=g[u].size();

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

        int v=g[u][i];

        if(pre[u]>pre[v]){

            if(!pre[v]){

                tarjans(v);

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

             }

            else

                low[u]=min(pre[v], low[u]);

         }

     }

     if(low[u]==pre[u]){

         ++scc_cnt;

         while(){

             int x=s.top();

             s.pop();

             scc[x]=scc_cnt;

             if(x==u) break;

         }

     }

 }

 int n, m;

 int main(){

     while(scanf("%d%d", &n, &m) && (n||m)){

         while(m--){

            int u, v;

            scanf("%d%d", &u, &v);

            g[u].push_back(v);

         }

         dfs_clock=;

         scc_cnt=;

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

           if(!scc[i])

              tarjans(i);

         int i;

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

             if(scc[i]!=scc[]){

                 printf("No\n");

                 break;

             }

         if(i>n)   printf("Yes\n");

         memset(pre, , sizeof(pre));

         memset(low, , sizeof(low));

         memset(scc, , sizeof(scc));

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

            g[i].clear();

     }

     return ;

}

 //思路三：
 1  #include<iostream>

  #include<cstring>

  #include<cstdio>

  #include<algorithm>

  #include<vector>

  #define N 10005

  using namespace std;

  vector<int>g[N];

  bool flag;

  int pre[N], low[N];

  int dfs_clock;

  void tarjans(int u){

      pre[u]=low[u]=++dfs_clock;

      int len=g[u].size();

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

         int v=g[u][i];

         if(!flag) return ;

         if(pre[u]>pre[v]){

             if(!pre[v]){

                 tarjans(v);

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

              }

             else

                 low[u]=min(pre[v], low[u]);

          }

      }

      if(low[u]==pre[u] && u!=)

          flag=false;

  }

  int n, m;

  int main(){

      while(scanf("%d%d", &n, &m) && (n||m)){

          while(m--){

             int u, v;

             scanf("%d%d", &u, &v);

             g[u].push_back(v);

          }

          dfs_clock=;

          flag=true;

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

            if(!pre[i]){

               if(!flag) break;

               tarjans(i);

            }

          if(!flag)  printf("No\n");

          else       printf("Yes\n");

          memset(pre, , sizeof(pre));

          memset(low, , sizeof(low));

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

             g[i].clear();

      }

      return ;

 }