开发者社区> 余二五> 正文

poj2186Popular Cows(Kosaraju算法--有向图的强连通分量的分解)

简介:
+关注继续查看

/*
   题目大意:有N个cows, M个关系
   a->b 表示 a认为b  popular;如果还有b->c, 那么就会有a->c 
   问最终有多少个cows被其他所有cows认为是popular!
   
   思路:强连通分量中每两个节点都是可达的! 通过分解得到最后一个连通分量A,
   如果将所有的强连通分量看成一个大的节点,那么A一定是孩子节点(因为我们先
   完成的是父亲节点的强连通分量)! 最后如果其他的强连通分量都可以指向A,那么
   A中的每一个cow都会被其他cows所有的cows认为popular! 
*/ 
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include<vector>
#define M 10005
using namespace std;

vector<int>ex[M];
vector<int>ey[M];

int n, m;
int cnt[M];//记录第一次dfs的节点的逆序
int vis[M];//标记节点是否已经被访问过了
int mark[M];//标记每一个节点是属于哪一个连通分量
int ans;
int top;

void dfs1(int u){//出度遍历 
    if(!vis[u]){
       vis[u]=1;
       int len=ex[u].size();
       for(int i=0; i<len; ++i){
           int v=ex[u][i];
           dfs1(v);
       }
       cnt[top++]=u;
    }
}

void dfs2(int u){//入度遍历 
   if(!vis[u]){
      vis[u]=1;
      mark[u]=ans;
      int len=ey[u].size();
      for(int i=0; i<len; ++i){
         int v=ey[u][i];
         dfs2(v);
      }
   }
}

int main(){
   while(scanf("%d%d", &n, &m)!=EOF){
      while(m--){
         int u, v;
         scanf("%d%d", &u, &v);
         ex[u].push_back(v);
         ey[v].push_back(u);
      }
      ans=top=0;
      for(int i=1; i<=n; ++i)
         if(!vis[i])
             dfs1(i);
      
      memset(vis, 0, sizeof(vis));

      for(int i=top-1; i>=0;  --i)
          if(!vis[cnt[i]]){
             ++ans;
             dfs2(cnt[i]);
          }
      int count=0;
      int u=0;
      for(int i=1; i<=n; ++i)
           if(mark[i]==ans){
              ++count;
              u=i;
           }
      memset(vis, 0, sizeof(vis));
      dfs2(u);

      for(int i=1; i<=n; ++i)//其他的强连通分量是否都指向了最后一个强连通分量 
        if(!vis[i]){
           count=0;
           break;
        }
      printf("%d\n", count);
      for(int i=1; i<=n; ++i){
         ex[i].clear();
         ey[i].clear();
      }
      memset(vis, 0, sizeof(vis));
   }
   return 0;
}
/*
tarjan 算法果然nb! 首先我们利用该算法将所有的强连通分量分开!
然后将每一个连通分量看成是一个点,这样就成了一个有向无环图!
接着判断初度为 0 的点一共有多少个!如果只有一个,那么最终的答案就是
这个节点终所有子节点的个数!也就是说这个节点中的每一个子节点都能 
其他的所有节点到达!

如果初度为 0 的点多余1个,那么对不起,不能满足某个节点恰好能被其他所有
的节点访问到! 
*/#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#define M 10005
using namespace std;

vector<int>edge[M];
stack<int>s;
int low[M], vis[M];
int sccN[M], pre[M];
int n, m;
int dfs_clock, cnt;

void dfs(int u){//tarjan 算法 
   int len = edge[u].size();
   pre[u]=low[u]=++dfs_clock;
   s.push(u);
   for(int i=0; i<len; ++i){
       int v=edge[u][i];
       if(!pre[v]){
          dfs(v);
          low[u]=min(low[u], low[v]);            
       } 
       else if(!sccN[v])
          low[u] = min(low[u], pre[v]);  
   }     
   if(low[u]==pre[u]){
       ++cnt;
       while(1){
         int v=s.top();
         s.pop();
         sccN[v]=cnt;
         if(u==v) break;
       }           
   }
}

int main(){
   while(scanf("%d%d", &n, &m)!=EOF){
       dfs_clock=cnt=0;
       memset(pre, 0, sizeof(pre));
       memset(sccN, 0, sizeof(sccN));
       memset(vis, 0, sizeof(vis));
       while(m--){
          int u, v;
          scanf("%d%d", &u, &v);
          edge[u].push_back(v);           
       }   
       for(int i=1; i<=n; ++i)
          if(!pre[i]) 
             dfs(i);
       int num=0;    
       for(int i=1; i<=n; ++i)
          if(sccN[i]==1)
             ++num;
       int count=0;
       memset(vis, 0, sizeof(vis));
       for(int i=1; i<=n; ++i){
           int len=edge[i].size();
           for(int j=0; j<len; ++j)
              if(sccN[i] != sccN[edge[i][j]]){
                 vis[sccN[i]]=1;
                 break;
              }        
       }
       
       for(int i=1; i<=cnt; ++i)
         if(!vis[i]) ++count;
       if(count==1)
          printf("%d\n", num);
       else printf("0\n");
       for(int i=1; i<=n; ++i)
          edge[i].clear();
       while(!s.empty())
          s.pop();
   }
   return 0;    
}
/*比较慢的方法就是:利用tarjan算法将所有的强连通分量进行分离之后,
 将每一个强连通分量看成是一个点,如果有满足我们答案的解,那么初度为零
 点一定只有一个,并且这个点的所有子节点的编号是 1!那么我们先计算出子节点
 编号为 1的个数, 然后在判断其他的强连通分量的节点是否能够到达编号为 1 的
 强连通分量! */
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#define M 10005
using namespace std;

vector<int>edge[M];
stack<int>s;
int low[M], vis[M], used[M];
int sccN[M], pre[M];
int n, m;
int dfs_clock, cnt, sum, xx;

void dfs(int u){
   int len = edge[u].size();
   pre[u]=low[u]=++dfs_clock;
   s.push(u);
   for(int i=0; i<len; ++i){
       int v=edge[u][i];
       if(!pre[v]){
          dfs(v);
          low[u]=min(low[u], low[v]);            
       } 
       else if(!sccN[v])
          low[u] = min(low[u], pre[v]);  
   }     
   if(low[u]==pre[u]){
       ++cnt;
       while(1){
         int v=s.top();
         s.pop();
         sccN[v]=cnt;
         if(u==v) break;
       }           
   }
}

int dfs2(int u){
    int len=edge[u].size();
    if(sccN[u]==1){//到达之后就不在进行任何搜索 
       sum+=xx;
       return 1;         
    }
    vis[u]=1;
    for(int i=0; i<len; ++i){
       int v=edge[u][i];
       if(!vis[v]){
           if(dfs2(v))
             return 1;      
       }
    }     
   return 0;
}

int main(){
   while(scanf("%d%d", &n, &m)!=EOF){
       dfs_clock=cnt=0;
       memset(pre, 0, sizeof(pre));
       memset(sccN, 0, sizeof(sccN));
       memset(vis, 0, sizeof(vis));
       memset(used, 0, sizeof(used));
       while(m--){
          int u, v;
          scanf("%d%d", &u, &v);
          edge[u].push_back(v);           
       }   
       for(int i=1; i<=n; ++i)
          if(!pre[i]) 
             dfs(i);
       int num=0;    
       sum=0;
       used[1]=1;
       for(int i=1; i<=n; ++i){
          
          if(sccN[i]==1)
             ++num;
          else if(!used[sccN[i]]){
             memset(vis, 0, sizeof(vis));
             xx=sccN[i];
             used[sccN[i]]=1; 
             dfs2(i);
          }
       }
       
       if(sum==(cnt+1)*cnt/2-1)//最后将能到达标号为1的连通分量的所有强连通分量的标号加起来 
          printf("%d\n", num);
       else printf("0\n");
       for(int i=1; i<=n; ++i)
          edge[i].clear();
       while(!s.empty())
          s.pop();
   }
   return 0;    
}









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3895221.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23526 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
22227 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
18586 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
14690 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36349 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15295 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14859 0
+关注
20380
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载