USACO Silver 2022 February - Redistributing Gifts

Official Analysis (C++)

Solution 1

See the official analysis.

Solution 2 - Strongly Connected Components

Explanation

Similar to the official analysis, we can construct a directed edge from $i$ to $j$ if cow $i$ prefers gift $j$ to gift $i$. If cow $i$ is able to receive a gift where it has an outgoing edge, then cow $i$ has received the most optimal gift it can be reassigned. Remember to also add an edge from cow $i$ to itself in case it cannot get a better gift.

Then, we can separate the graph into strongly connected components (SCCs). If $i$ is in an SCC, this means that cow $i$ can receive all gifts in the SCC through a series of reassignments by definition of an SCC. The SCC must also have at least one of cow $i$'s preferred gift because it must contain at least one outgoing edge from $i$. If a cow does not belong in an SCC, it cannot receive a more optimal reassignment.

Implementation

Kosaraju's algorithm can be used to find all SCCs in the graph. At the end, it is optimal to just go down cow $i$'s preference list and assign the first gift belonging in the SCC.

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <bits/stdc++.h>

using namespace std;
const int N = 501;

// The adjacency lists for the graph (revgraph is reversed)
vector<int> graph[N], revgraph[N];
vector<bool> vis(N), vis2(N);
vector<int> path;