设为首页 加入收藏

TOP

POJ2186 Popular Cows ,有向图, Tarjan算法
2015-07-20 17:41:08 来源: 作者: 【 】 浏览:1
Tags:POJ2186 Popular Cows 向图 Tarjan 算法

题意:

给定一个有向图,求有多少个顶点是由任何顶点出发都可达的。

顶点数<= 10,000,边数 <= 50,000


定理:
有向无环图中唯一出度为0的点,一定可以由任何点出发均可达
(由于无环,所以从任何点出发往前走,必然终止于一个出度为0的点)



1. 求出所有强连通分量
2. 每个强连通分量缩成一点,则形成一个有向无环图DAG。
3. DAG上面如果有唯一的出度为0的点,则该点能被所有的点可达。那么该点所代表的连通分量上的所有的原图中的点,都能被原图中的所有点可达,则该连通分量的点数,就是答案。
4. DAG上面如果有不止一个出度为0的点,则这些点互相不可达,原问题无解,答案为0


#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int maxn = 10000 + 100; vector
        
          g[maxn]; int dfn[maxn], low[maxn], belong[maxn], dfs_clock, scc_cnt, size[maxn]; stack
         
           s; int n, m; void dfs(int u){ dfn[u] = low[u] = ++dfs_clock; s.push(u); for(int i=0; i
          
           

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇HDU 5014 Number Sequence(贪心) 下一篇九度_题目1352:和为S的两个数字

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·用 C 语言或者限制使 (2025-12-25 08:50:05)
·C++构造shared_ptr为 (2025-12-25 08:50:01)
·既然引用计数在做 GC (2025-12-25 08:49:59)
·Java 编程和 c 语言 (2025-12-25 08:19:48)
·. net内存管理宝典这 (2025-12-25 08:19:46)