The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

Preface: This solution may be rather verbose. I did not solve the problem during the contest, so I wrote the solution mainly to organize my own thoughts. If you already have the idea and only made a mistake in the implementation, I recommend jumping directly to the code section.

update@2022/3/13: Thanks to @小木虫 for the reminder: the current solution is not a correct solution! If USACO’s test data were strong enough, the Hungarian algorithm used here would not pass this problem because its complexity is $O(nm)$ . If you want to implement my bipartite-matching plus topological approach, you can use Dinic’s algorithm to find the maximum bipartite matching, although it is more troublesome to write. When I have time, I will also try implementing this solution with Dinic and update the solution.

The reading experience is better on the blog

1: Problem Statement

There are $N$ cows and $M$ types of cereal, with one box of each type. Every cow has a first and a second favorite cereal type, referred to below as its first and second choices. A cow first chooses its favorite cereal; if that cereal is occupied, it chooses its second favorite. Determine:

The minimum possible number of cows that receive no cereal.
An ordering of the cows that achieves this minimum.

2: Analysis

2.1 First Question

For the first question, we can see that this is a standard maximum bipartite-matching problem, and it is easy to think of solving it with the Hungarian algorithm (although I did not think of this during the contest). Readers unfamiliar with the Hungarian algorithm and bipartite matching can refer to the solutions for the template problem. This solution will focus mainly on the second question.

2.2 Second Question

For the second question, my initial idea was to output the cows successfully matched to their first choices, then the cows successfully matched to their second choices, and finally the unmatched cows. The resulting submission passed only the sample. With guidance from @lutongyu, I finally understood the problem with this approach.

More specifically, it is fine to output cows successfully matched to their first choices first, and it is also fine to output unmatched cows last. The real problem is the order of the second-choice cows. Consider the following data, shown in the figure below:

1
2
3

1 (cow) -> [1 (fir), 2 (sec)]
2 (cow) -> [1 (fir), 3 (sec)] 
3 (cow) -> [3 (fir), 4 (sec)]

We can manually simulate these data.

First try the optimal ordering 1 2 3:

$\text{Cow}_1$ first takes its first choice, cereal 1.
Because $\text{Cow}_2$ ’s first choice is occupied by $\text{Cow}_1$ , it takes its second choice, cereal 3.
$\text{Cow}_3$ ’s first choice is occupied by $\text{Cow}_2$ , so it takes its second choice, cereal 4.

In this case, every cow receives cereal.

Now swap the order of $\text{Cow}_2$ and $\text{Cow}_3$ , obtaining the ordering 1 3 2 and the following simulation:

$\text{Cow}_1$ takes its first choice, cereal 1.
$\text{Cow}_3$ takes its first choice, cereal 3.
Both the first and second choices of $\text{Cow}_2$ are occupied—cereals 1 and 3—so it cannot receive cereal.

In this case, $\text{Cow}_2$ cannot receive any cereal.

These data show that directly outputting cows matched to their second choices does not work. Some additional processing is necessary when outputting second-choice cows to ensure that the ordering still attains the maximum matching size.

More specifically, we can use an algorithm similar to topological sorting to resolve conflicts among second-choice cows.

First consider what happens when a cow is successfully matched to its first choice and that cereal is also another cow’s first choice. Using $\text{Cow}_1$ in the preceding figure as an example, it affects the choice of $\text{Cow}_2$ : $\text{Cow}_1$ occupies $\text{Cow}_2$ ’s first choice, forcing it to select its second choice. $\text{Cow}_2$ then affects $\text{Cow}_3$ ’s choice: $\text{Cow}_2$ occupies $\text{Cow}_3$ ’s first choice, forcing it to select its second choice. From this observation, we find that outputting cows along such an “influence chain” guarantees the maximum matching.

3: Algorithm

The beginning of such a chain must be a cow successfully matched to its first choice that forces another cow to choose its second choice; that is, this cow’s first choice is also another cow’s first choice. Enqueue all such cows. Next consider the affected cows. To discover the influence chain, we must also enqueue these affected cows, because they can choose only their second choices, and their second choices may occupy the first choices of other cows, just as $\text{Cow}_2$ does in the figure.

To find which cows might be affected, introduce a dynamic array inv_e[i], implemented as an adjacency list, that contains every cow whose first choice is cereal i. Only a cow whose first choice was taken by another cow can be affected.

For example, in the preceding figure, inv_e[1] = [ $\text{Cow}_1$ , $\text{Cow}_2$ ].

The Hungarian algorithm uses a matched[i] array. Its index denotes a node on the right side, and its value denotes the left-side node matched to that right-side node. In this problem, the index of matched[i] is a cereal number, and its value is the cow matched to that cereal. We can introduce an inv_match[i] array whose index is a cow and whose value is a cereal. Through inv_match, we can determine which cereal each cow is ultimately matched to—its first choice, its second choice, or no match.

Using the preceding figure as an example, inv_match[ $\text{Cow}_2$ ] equals cereal 3, because cereal 3 is its final match.

The following code shows how to find every cow affected by a first-choice cow:

for(int i = 1; i <= n; i++){              // i traverses cows successfully matched to their first choices.
    if(invmatched[i] != e[i][0]) continue;// e[i][0] denotes cow i's first choice.
                                          // invmatched[i] is the cereal ultimately matched to cow i.
                                          // Thus, continue immediately if it was not matched to its first choice.
    printf("%d\n",i);// If it was matched to its first choice, output it directly.

    for(int cur:inve[e[i][0]]){         // Traverse cows that may be affected by the current first-choice cow.
                                        // e[i][0] is cow i's first choice, and cow i is certainly matched to it.
                                        // inve[e[i][0]] contains every cow with the same first choice as cow i.
        if(invmatched[cur] == e[cur][1])// invmatched[cur] is the cereal ultimately matched to cow cur,
                                        // while e[cur][1] is cow cur's second choice.
        {                               // This ensures cur ultimately took its second choice, meaning it was affected;
                                        // it also prevents cow i itself from being enqueued.
            q.push(cur);
        }
    }
}

Next, the second choices of cows already in the queue may occupy other cows’ first choices. We can therefore use a similar method to find the remainder of this influence chain:

while(!q.empty()){
    int cur = q.front();
    printf("%d\n",cur);// The queue is FIFO, so output cows higher in the influence chain first.
    q.pop();
    for(int nex:inve[e[cur][1]]){         // e[cur][1] is the second choice of cow cur.
                                          // inve[e[cur][1]] contains every cow that treats cur's second choice as
                                          // its first choice—that is, every cow that cur might affect.
        if(invmatched[nex] == e[nex][1]) {// It ultimately took its second choice, so this cow was affected.
            q.push(nex);
        }
    }
}

4: Code Implementation and Details

Finally, here is the complete code, with comments explaining the details:

/*Date: 22 - 02-03 22 19
PROBLEM_NUM: P8095 [USACO22JAN] Cereal 2 S*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n, m;
vector<int> e[MAXN], inve[MAXN];
queue<int> q;
int vised[MAXN], matched[MAXN];
int invmatched[MAXN];

bool found(int cur){// Hungarian algorithm
    for(int nex:e[cur]){
        if(vised[nex]) continue;
        vised[nex] = true;
        if(!matched[nex] || found(matched[nex])){
            matched[nex] = cur;
            invmatched[cur] = nex;
            vised[nex] = false;
            return true;
        }
    }
    return false;
}

int main(){
    int match_cnt = 0;
    scanf("%d%d",&n,&m);
    for(int i = 1; i<=n; i++){
        int f,s;
        scanf("%d%d",&f,&s);
        e[i].push_back(f);   // e[i][0] is cow i's first choice.
        e[i].push_back(s);   // e[i][1] is cow i's second choice.
        inve[f].push_back(i);// inve[f] contains every cow whose first choice is cereal f.
    }
    for(int i = 1;i <= n; i++){// Hungarian-algorithm portion
        if(found(i)){
            match_cnt++;
        }
    }

    printf("%d\n", n - match_cnt);// Hungry cows = all cows - cows that received cereal.

    for(int i = 1; i <= n; i++){          // i traverses cows successfully matched to their first choices.
    if(invmatched[i] != e[i][0]) continue;// Continue immediately if the match is not the first choice.
    printf("%d\n",i);                     // Output a first-choice cow directly.

    for(int cur:inve[e[i][0]]){         // Traverse cows that may be affected by the current first-choice cow.
                                        // e[i][0] is cow i's first choice, and cow i is matched to it.
                                        // inve[e[i][0]] contains all cows with the same first choice as cow i.
        if(invmatched[cur] == e[cur][1])// invmatched[cur] is the cereal ultimately matched to cow cur,
                                        // while e[cur][1] is cow cur's second choice.
            {                           // Ensure cur ultimately took its second choice, meaning it was affected;
                                        // this also prevents cow i itself from being enqueued.
                q.push(cur);
            }
        }
    }
    
    while(!q.empty()){
        int cur = q.front();
        printf("%d\n",cur);// FIFO lets us output cows higher in the influence chain first.
        q.pop();
        for(int nex:inve[e[cur][1]]){         // e[cur][1] is cow cur's second choice.
                                              // inve[e[cur][1]] contains every cow whose first choice is cur's
                                              // second choice—that is, cows that cur might affect.
            if(invmatched[nex] == e[nex][1]) {// It ultimately took its second choice, meaning it was affected.
                q.push(nex);
            }
        }
    }

    for(int i = 1; i<=n; i++){// Finally output cows that were not successfully matched.
        if(!invmatched[i]){   // invmatched[i] == 0 means cow i was not matched to any cereal.
            printf("%d\n",i);
        }
    }

    system("pause");
}

Finally, I hope this solution can help you. If you still do not understand something or discover a problem in the solution, you can send me a private message or point it out in the comments. I will try my best to answer or resolve it.