USACO Silver 2020 January - Wormhole Sort

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: $\mathcal{O}(N\log N)$

Like the DFS solution, we binary search on the answer $x$. $x$ is valid if all $p_i$ are in the same component as $i$, which we can query in $\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: $\mathcal{O}(N + M\log M)$

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

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

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)