C - Book 拓扑排序-蒲公英云

C - Book 拓扑排序

https://codeforces.com/contest/1573/problem/C

判断还有度的节点一定放在最后
注意更新的操作：如果比当前节点小，当前节点加一再比较，否则直接比较
最后输出最大的操作次数就可以。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> to[N];
int main() { 
    ios::sync_with_stdio(false); cin.tie(0);
    int t; cin >> t;
    while (t--) { 
        int n; cin >> n;
        for (int i = 0; i < n; i++) to[i].clear();
        vector<int> in(n);
        for (int i = 0; i < n; i++) { 
            int x; cin >> x;
            for (int j = 0; j < x; j++) { 
                int k; cin >> k;
                k--;
                to[k].push_back(i); // 邻接表，存下一个节点
                in[i]++;
            }
        }
        queue<int> q;
        vector<int> ts(n);
        for (int i = 0; i < n; i++) { 
            if (in[i] == 0) { 
                q.push(i); // 存入度为0的点
                ts[i] = 1;
            }
        }
        while (!q.empty()) { 
            int u = q.front(); q.pop();
            for (auto v : to[u]) {   // 入度为0的下一个节点
                in[v]--; // 入度减少一
                if (v < u) ts[v] = max(ts[v], ts[u] + 1); 
                // 如果 下一个更新的节点比当前节点小，当前节点要多更新一次，才会更新到下一个节点
                else ts[v] = max(ts[v], ts[u]);
                // 待更新的节点 比 当前节点大，那么只需要比较跟新的次数
                if (!in[v])q.push(v); 
            }
        }
        int ok = 1;
        for(int i = 0; i < n; i++)
            if(in[i]) { ok = 0; break;}
        if(!ok) {  cout << "-1\n"; continue; }
        cout << *max_element(ts.begin(),ts.end()) << '\n';
    }
}