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

简介:

/*
          题意: 给你一个图,求这个有向图示否是一个强连通图(每两个节点都是可以相互到达的)!
          思路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=0; 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(1){
             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=0;
         scc_cnt=0;
         for(int i=1; i<=n; ++i)
           if(!scc[i])
              tarjans(i);
         int i;
         for(i=2; i<=n; ++i)
             if(scc[i]!=scc[1]){
                 printf("No\n");
                 break;
             }
         if(i>n)   printf("Yes\n");
         memset(pre, 0, sizeof(pre));
         memset(low, 0, sizeof(low));
         memset(scc, 0, sizeof(scc));
         for(i=1; i<=n; ++i)
            g[i].clear();
     }
     return 0;    
}



 //思路三:
 #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=0; 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!=1)
         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=0;
         flag=true;
         for(int i=1; i<=n; ++i)
           if(!pre[i]){
              if(!flag) break;
              tarjans(i);
           }

         if(!flag)  printf("No\n");
         else       printf("Yes\n");
         memset(pre, 0, sizeof(pre));
         memset(low, 0, sizeof(low));
         for(int i=1; i<=n; ++i)
            g[i].clear();
     }
     return 0;    
}

目录
相关文章
|
存储 C++
欧拉回路和欧拉路径
欧拉回路和欧拉路径
70 0
欧拉回路和欧拉路径
洛谷P1605:迷宫
洛谷P1605:迷宫
84 0
洛谷 P1141 01迷宫
洛谷 P1141 01迷宫
77 0
AcWing——方格迷宫(有点不一样的迷宫问题)
AcWing——方格迷宫(有点不一样的迷宫问题)
89 0
|
存储
Leetcode-每日一题1210. 穿过迷宫的最少移动次数(BFS)
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_46618592/article/details/128890280?spm=1001.2014.3001.5501
114 0
Leetcode-每日一题1210. 穿过迷宫的最少移动次数(BFS)
HDU-致命武器(线段树)
HDU-致命武器(线段树)
89 0
【LeetCode286】墙与门(BFS)
-1 表示墙或是障碍物 0 表示一扇门
202 0
【LeetCode286】墙与门(BFS)