USACO Silver 2020 January - Wormhole Sort

Authors: Óscar Garries, Neo Wang

Solution 1 - DFS

Official Analysis

Implementation

#include <bits/stdc++.h>
using namespace std;
const int MX = 1e5;
vector<pair<int, int>> g[MX];
vector<int> ar(MX), component(MX);
int n, m;

Solution 2 - DSU/UF + Binary Search

Time Complexity: O(NlogN)\mathcal{O}(N\log N)

Like the DFS solution, we binary search on the answer xx. xx is valid if all pip_i are in the same component as ii, which we can query in O(α(N))\mathcal{O}(\alpha(N)) using a Union Find/Disjoint Set data structure.

Implementation

#include <bits/stdc++.h>
using namespace std;
#define vt vector
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, a, b) for(int i = (a); i <= (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); i++)
#define trav(a, x) for (auto& a : x)

Solution 3 - DSU/UF

Time Complexity: O(N+MlogM)\mathcal{O}(N + M\log M)

We can alternatively search for our weight by adding the weights greatest \rightarrow least until all pip_i are in the same component as ii.

Our resulting time complexity is O(N)\mathcal{O}(N) after an initial sorting of the weights.

Implementation

C++

#include <bits/stdc++.h>
using namespace std;
#define vt vector
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, a, b) for(int i = (a); i <= (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); i++)
#define trav(a, x) for (auto& a : x)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!