USACO Bronze 2019 December - Livestock Lineup

Official Analysis (C++)

Solution w/ Graphs

What if there were up to $10^5$ cows? Then neither of the solutions provided in the analysis would be fast enough.

Say that we draw an edge between two cows if they must be adjacent. Then if a solution exists, the graph must be a union of paths.

(insert diagram)

We iterate over the cows in increasing lexicographical order. If a cow is not yet part of the answer and it is the endpoint of a path, then we add the entire path containing the cow to the answer.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;