Milking Order

在图上考虑问题，将一个观察结果中相邻牛间加上有向边。可以发现，如果前 $X$ 个观察结果可以被满足，充要条件就是这时的图存在拓扑排序。如果使用BFS算法求拓扑排序，那么如果多次迭代后，入度为0的节点总数等于总节点数，就是成功，否则图中有环，不存在拓扑排序。复杂度是 ${\mathcal{O}(n)}$ 。

而要找到这个最大的 $X$ ，可以对 $X$ 进行二分查找，这时整体复杂度变成 ${\mathcal{O}(n\log{n})}$ 。

最后我们要生成字母序最小的结果，就是需要对BFS的拓扑排序算法做一点变化，将queue换成priority queue就可以了，注意我们要的是小头的堆。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m;
vector<int> order[50005];
 
// check if the first x orders can be satisfied
bool check(int x) {
    vector<vector<int>> adj;
    vector<int> in_degree;
    adj.resize(n+1);
    in_degree.resize(n+1);
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < order[i].size()-1; j++) {
            int u = order[i][j], v = order[i][j+1];
            adj[u].push_back(v);
            in_degree[v]++;
        }
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in_degree[i] == 0) q.push(i);
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt++;
        for (int v: adj[u])
            if ((--in_degree[v])==0) q.push(v);
    }
    return cnt == n;
}
 
int main() {
    freopen("milkorder.in", "r", stdin);
    freopen("milkorder.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int k;
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            int o;
            scanf("%d", &o);
            order[i].push_back(o);
        }
    }
 
    int lo = 0, hi = m;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (check(mid))
            lo = mid;
        else 
            hi = mid - 1;
    }
 
    int X = lo;
    vector<vector<int>> adj;
    vector<int> in_degree;
    adj.resize(n+1);
    in_degree.resize(n+1);
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < order[i].size()-1; j++) {
            int u = order[i][j], v = order[i][j+1];
            adj[u].push_back(v);
            in_degree[v]++;
        }
    }
 
    priority_queue<int, vector<int>, greater<int>> q;
    vector<int> ans;
    for (int i = 1; i <= n; i++)
        if (in_degree[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        ans.push_back(u);
        for (int v: adj[u])
            if ((--in_degree[v])==0) q.push(v);
    }
 
    for (int i = 0; i < ans.size(); i++) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
 
    return 0;
}