设为首页 加入收藏

TOP

POJ2186 Popular Cows ,有向图, Tarjan算法
2015-07-20 17:41:08 来源: 作者: 【 】 浏览:2
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的两个数字

评论

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

·Start, Stop, and Di (2025-12-25 14:50:57)
·C语言入门教程:零基 (2025-12-25 14:50:54)
·【全600集】2025年全 (2025-12-25 14:50:51)
·为什么C语言中结构体 (2025-12-25 14:20:29)
·小白提问:C语言中怎 (2025-12-25 14:20:27)