Cereal 2 (USACO Silver 2022 January)

图上建模：用点代表麦片，有向边代表牛，A->B表示这条边对应的牛更喜欢A麦片。

首先按题目提示，可以按连通分量来处理，我们只需要考虑一个连通分量内部的情况，就可以推广到全局。

直观观察，导致一些牛吃不到麦片的原因，是比较"popular"的麦片被其它牛先抢走了，换句话说牛按它的喜好顺序选择麦片，是不能最优的主要原因。

举个例子：

如果A牛先吃选择了麦片2，然后C牛再吃选择了麦片3，然后B牛就只能挨饿了。而如果按ABC这样的顺序吃，则三头牛都能吃到。

现在就是需要想办法构造出这个顺序来，让最多牛可以吃到麦片：

考虑一个连通分量，如果这个连通分量是最简单情况——一棵树（共x个节点），那我们发现，可以吃掉x-1个麦片：从任何边出发，按DFS顺序吃麦片，直到最后剩下一个节点，就可以了。
如果这个连通分量不是树，而是有更多边，那我们发现应该从任何一条“非树边”出发，然后就可以不用剩下麦片，可以把x个节点全部吃完。

所以整理下思路，可以设计如下的算法：

建边，A->B表示一头牛吃A、B麦片，同时更喜欢A。
从每个点出发dfs（不考虑边的方向），经过的边就是“树边”，都标注出来。
如果存在非树边，选择一条非树边，否则任选一条边出发，然后dfs吃麦片，直到没有麦片可以吃。
重复3，直到所有麦片都被吃完，或所有牛都用完。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n,m;
 
pair<int,int> edges[100005];
bool tree[100005];
vector<int> todo;           // edges to process
 
vector<int> adj[100005];    // edge indexes
vector<int> adj0[100005];   // 无向图
bool vis[100005];
bool eaten[100005];         // cow has eaten
bool gone[100005];          // cereal is gone
 
vector<int> ans;
bool printed[100005];
 
// mark all tree edges
void dfs1(int x) {
    vis[x] = true;
    for (int i: adj0[x]) {
        int y = edges[i].first == x ? edges[i].second : edges[i].first;
        if (!vis[y]) {
            tree[i] = true;
            dfs1(y);
        }
    }
}
 
// start from a cow and recursively eat cereals
void dfs2(int e) {
    eaten[e] = true;
    ans.push_back(e);
    int x = !gone[edges[e].first] ? edges[e].first : edges[e].second;
    gone[x] = true;
    for (int i: adj0[x]) {
        if (eaten[i] || gone[edges[i].first] && gone[edges[i].second]) continue;
        dfs2(i);
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int a,b;
        scanf("%d %d", &a, &b);
        edges[i] = {a,b};
        adj[a].push_back(i);
        adj0[a].push_back(i);
        adj0[b].push_back(i);
    }
    for (int i = 1; i <= m; i++) {   // mark all tree edges
        if (!vis[i]) {
            dfs1(i);
        }
    }
    for (int i=1; i<=n; i++) if (!tree[i]) todo.push_back(i);
    for (int i=1; i<=n; i++) if (tree[i]) todo.push_back(i);
    for (int e: todo) {     // non-tree edge first, then tree edges
        if (eaten[e] || gone[edges[e].first] && gone[edges[e].second]) continue;
        dfs2(e);
    }
    printf("%d\n", n-(int)ans.size());
    for (int e: ans) {
        printf("%d\n", e);
        printed[e] = true;
    }
    for (int i=1; i<=n; i++) if (!printed[i]) printf("%d\n", i);
    return 0;
}