# 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: $\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

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!