USACO 2020 January Contest Silver Division - Wormhole Sort

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Binary search for the min width. For each step of the binary search, we apply DFS to check whether that minimal width is achievable.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<bool> visited(1e5 + 1);
vector<int> locs(1e5 + 1);
vector<int> indices(1e5 + 1);
vector<vector<pair<int, int>>> adj(1e5 + 1, vector<pair<int, int>>(0));

void dfs(int start, int min_width) {
    visited[start] = true;
    for (pair<int, int> a : adj[start]) {
        if (a.second >= min_width && !visited[a.first]) {
            dfs(a.first, min_width);
        }
    }
}

bool ok(int min_width) {
    fill(visited.begin(), visited.end(), false);
    dfs(1, min_width);
    for (int i = 1; i <= n; i++) {
        if (!visited[i] && locs[i] != i) {
            return false;
        }
    }
    return true;
}

int main() {
    freopen("wormsort.in", "r", stdin);
    freopen("wormsort.out", "w", stdout);

    cin >> n >> m;
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        cin >> locs[i];
        if (locs[i] != i) {
            flag = false;
        }
        indices[locs[i]] = i;
    }
    if (flag) {
        cout << -1 << endl;
        return 0;
    }

    int r = 0;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[indices[b]].push_back({indices[a], w});
        adj[indices[a]].push_back({indices[b], w});
        r = max(r, w);
    }

    int l = 0;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (ok(mid)) {
            l = mid + 1;
        } 
        else {
            r = mid - 1;
        }
    }
    cout << l - 1 << "\n";
    return 0;
}