POJ 2367 Genealogical tree-白红宇

POJ 2367 Genealogical tree

阅读量：5235 次

发布时间：2019-06-14

本文共 841 字，大约阅读时间需要 2 分钟。

很耿直的拓扑排序题，就当熟悉一下算法吧。。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #define FF(i, a, b) for(int i=a; i
               
                b; i--)#define REP(i, n) for(int i=0; i

G[maxn];inline void init(){ REP(i, maxn) G[i].clear(); CLR(in, 0); tot = 0;}inline void add(int u, int v){ G[u].push_back(v); in[v]++;}void topo(){ queue

q; FF(i, 1, n+1) if(!in[i]) q.push(i); while(!q.empty()) { int u = q.front(); q.pop(); ans[tot++] = u; int nc = G[u].size(); REP(i, nc) { int v = G[u][i]; in[v]--; if(!in[v]) q.push(v); } }}int main(){ while(~scanf("%d", &n)) { init(); FF(i, 1, n+1) while(scanf("%d", &v), v) add(i, v); topo(); REP(i ,n) printf("%d%c", ans[i], i == n-1 ? '\n' : ' '); } return 0;}

转载于:https://www.cnblogs.com/jiangu66/p/3201423.html

你可能感兴趣的文章