AcWing 1191. 家谱树（拓扑排序的两种方式）

Love The Way You Lie 2022-09-12 10:49 183阅读 0赞

比较推荐第一种，上一篇题目的要求需要进行多次拓扑排序，

每次需要memset很多东西，而且不好确定范围。

#include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <vector>
    
    const int N = 110;
    
    int n;
    std::vector<int> to[N];
    
    
    int main()
    { 
        int n; scanf("%d", &n);
        
        std::vector<int> in(n+10);
        
        for (int i = 1; i <= n; i ++ )
        { 
            int son;
            while(scanf("%d",&son) and son > 0)
            { 
                to[i].push_back(son);
                in[son]++;
            }
        }
        
        std::queue<int> q;
        
        for(int i = 1; i <= n; i++)
            if(!in[i]) q.push(i), printf("%d ",i);
            
        while(q.size())
        { 
            int u = q.front(); q.pop();
            for(int v : to[u])
            { 
                if(--in[v] == 0)
                { 
                    printf("%d ",v);
                    q.push(v);
                }
            }
        }
        
        return 0;
    }

#include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    
    const int N =  110, M = N * N / 2;
    
    int n;
    int h[N], e[M], ne[M], idx;
    int q[N], d[N];
    
    inline  void add(int a, int b)
    { 
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    void topsort()
    { 
        int hh = 0, tt = -1;
    
        // d[i] 存储点i的入度
        for (int i = 1; i <= n; i ++ )
            if (!d[i])
                q[ ++ tt] = i;
    
        while (hh <= tt)
        { 
            int t = q[hh ++ ];
    
            for (int i = h[t]; i != -1; i = ne[i])
            { 
                int j = e[i];
                if (-- d[j] == 0)
                    q[ ++ tt] = j;
            }
        }
    }
    
    
    int main()
    { 
        scanf("%d", &n);
        
        memset(h, -1, sizeof h);
        
        for (int i = 1; i <= n; i ++ )
        { 
            int t;
            while(scanf("%d",&t) and  t>0) 
            { 
                add(i, t);
                d[t]++;
            }
        }
        
        topsort();
        
        for(int i = 0; i < n; i++) printf("%d ", q[i]);
        
        return 0;
    }