POJ2186 Popular Cows 强连通 Tarjan - c++编程基础

强连通的模版题，Kosaraju,Tarjan,Garbow三种随便选一种就可以了，三种算法的复杂度都是一样的O(n+m)，题意是有N头牛M种关系，牛之间会产生仰慕感，而且会传递，比如说A仰慕B，B仰慕C，那么A仰慕C，问有几头牛是被所有的牛仰慕的

这里我们可以看到一般如果 A->B,B->C,C->A,形成环的话也就是强连通形成时，这三个牛任何一个仰慕其它牛，也就代表着三头都仰慕其它的，一头被其它的仰慕，那么三头都会被其它牛仰慕，所以可以采用缩点的方法，意思就是这三个牛其实相当于一头牛

先运用强连通算法，将其中所有的分量染色。，染色的过程中也可以同时计算出分量中点的个数，然后进行缩点和重新构图的过程，将分量编号并且将几何中的元素的边转移到分量上来，即构建一个分量之间的有向图，构建的同时可以统计出每个分量的出度，最后一个统计出出度为0的分量的个数，然后具体输出个数

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // const int N = 10000 + 5; typedef struct Node { int to,nex; }; Node edge[N * 5]; int head[N],dfn[N],low[N],id[N],Stack[N];//dfn[v]表示顶点v被访问的hi见，为low[u]表示，从u点能回到的最早被遍历的点的dfs序号。 bool vis[N]; int scc_num; int t; int k; void clear() { memset(vis,false,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(head,-1,sizeof(head)); } void addedge(int a,int b,int i) { edge[i].to = b; edge[i].nex = head[a]; head[a] = i; } void tarjan(int v) { dfn[v] = low[v] = ++t; Stack[++k] = v; vis[v] = true; for(int i=head[v];i!=-1;i=edge[i].nex) { int u = edge[i].to; if(!dfn[u]) { tarjan(u); low[v] = min(low[v],low[u]); } else if(vis[u]) low[v] = min(low[v],dfn[u]); } if(low[v] == dfn[v]) { ++scc_num; int u; do { u = Stack[k]; k--; vis[u] = false; id[u] = scc_num; }while(u != v); } return ; } void cal(int n) { scc_num = 0; for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=edge[j].nex) if(id[i] != id[edge[j].to]) vis[id[i]] = true; } int main() { int n,m; while(scanf("%d %d",&n,&m) == 2) { clear(); int a,b; for(int i=0;i
                    
                      1) puts("0"); else { mark = 0; for(int i=1;i<=n;i++) if(id[i] == p) mark++; printf("%d\n",mark); } } return EXIT_SUCCESS; }