poj 2186 Popular Cows ：求能被有多少点是能被所有点到达的点 tarjan O(E)

  1 /**
  2 problem: http://poj.org/problem?id=2186
  3 
  4 当出度为0的点（可能是缩点后的点）只有一个时就存在被所有牛崇拜的牛
  5 因为如果存在有两个及以上出度为0的点的话，他们不会互相崇拜所以不存在被所有牛崇拜的牛
  6 牛的个数即该出度为0点（由环缩点而来）有多少牛
  7 **/
  8 #include<stdio.h>
  9 #include<stack>
 10 #include<algorithm>
 11 using namespace std;
 12 
 13 class Graphics{
 14     const static int MAXN = 10005;
 15     const static int MAXM = 50005;
 16 private:
 17     struct Edge{
 18         int to, next;
 19     }edge[MAXM];
 20     struct Point{
 21         int dfn, low, color;
 22     }point[MAXN];
 23     int sign, dfnNum, colorNum, sumOfPoint, first[MAXN], count[MAXN];
 24     bool vis[MAXN];
 25     stack<int> stk;
 26     void tarjan(int u){
 27         point[u].dfn = ++dfnNum;
 28         point[u].low = dfnNum;
 29         vis[u] = true;
 30         stk.push(u);
 31         for(int i = first[u]; i != -1; i = edge[i].next){
 32             int to = edge[i].to;
 33             if(!point[to].dfn){
 34                 tarjan(to);
 35                 point[u].low = min(point[to].low, point[u].low);
 36             }else if(vis[to]){
 37                 point[u].low = min(point[to].dfn, point[u].low);
 38             }
 39         }
 40         if(point[u].dfn == point[u].low){
 41             vis[u] = false;
 42             point[u].color = ++colorNum;
 43             count[colorNum] ++;
 44             while(stk.top() != u){
 45                 vis[stk.top()] = false;
 46                 point[stk.top()].color = colorNum;
 47                 count[colorNum] ++;
 48                 stk.pop();
 49             }
 50             stk.pop();
 51         }
 52     }
 53 public:
 54     void clear(int n){
 55         sign = dfnNum = colorNum = 0;
 56         for(int i = 1; i <= n; i ++){
 57             first[i] = -1;
 58             vis[i] = 0;
 59             count[i] = 0;
 60         }
 61         sumOfPoint = n;
 62         while(!stk.empty()) stk.pop();
 63     }
 64     void addEdgeOneWay(int u, int v){
 65         edge[sign].to = v;
 66         edge[sign].next = first[u];
 67         first[u] = sign ++;
 68     }
 69     void addEdgeTwoWay(int u, int v){
 70         addEdgeOneWay(u, v);
 71         addEdgeOneWay(v, u);
 72     }
 73     void tarjanAllPoint(){
 74         for(int i = 1; i <= sumOfPoint; i ++){
 75             if(!point[i].dfn)
 76                 tarjan(i);
 77         }
 78     }
 79     int getAns(){
 80         int ans = 0, ans2 = 0;
 81         int *outdegree = new int[sumOfPoint+1];
 82         for(int i = 1; i <= sumOfPoint; i ++){
 83             outdegree[i] = 0;
 84         }
 85         tarjanAllPoint();
 86         for(int i = 1; i <= sumOfPoint; i ++){
 87             for(int j = first[i]; j != -1; j = edge[j].next){
 88                 int to = edge[j].to;
 89                 if(point[to].color != point[i].color){
 90                     outdegree[point[i].color] ++;
 91                 }
 92             }
 93         }
 94         for(int i = 1; i <= colorNum; i ++){
 95             if(!outdegree[i]){
 96                 ans ++;
 97                 ans2 = count[i];
 98             }
 99         }
100         delete []outdegree;
101         if(ans == 1){
102             return ans2;
103         }else{
104             return 0;
105         }
106     }
107 }graph;
108 
109 int main(){
110     int n, m;
111     scanf("%d%d", &n, &m);
112     graph.clear(n);
113     while(m --){
114         int a, b;
115         scanf("%d%d", &a, &b);
116         graph.addEdgeOneWay(a, b);
117     }
118     printf("%d
", graph.getAns());
119     return 0;
120 }