solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif
struct DSU {
    std::vector<int> f;
    DSU(int n) : f(n) { std::iota(f.begin(), f.end(), 0); }
    int leader(int x) {
        if (f[x] == x) {
            return x;
        }
        int y = leader(f[x]);
        f[x] = y;
        return f[x];
    }
    bool merge(int a, int b) {
        auto x = leader(a);
        auto y = leader(b);
        if (x == y) {
            return false;
        }
        f[x] = y;
        return true;
    }
};

typedef pair<int, int> pii;
class Solution {
   public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<vector<pii>> revV(n + 1);
        for (int i = 0; i < n; i++) {
            int u = edges[i][0], v = edges[i][1];
            revV[v].push_back({u, i});
        }

        auto work = [&](int idx) {
            DSU dsu(n + 1);
            for (int i = 0; i < n; i++) {
                if (i == idx) continue;
                int u = edges[i][0], v = edges[i][1];
                dsu.merge(u, v);
            }
            for (int i = 2; i <= n; i++) {
                if (dsu.leader(1) != dsu.leader(i)) return false;
            }
            return true;
        };

        for (int i = 1; i <= n; i++) {
            if (revV[i].size() == 2) {
                bool ok1 = work(revV[i][1].second);
                if (ok1) {
                    return edges[revV[i][1].second];
                }
                return edges[revV[i][0].second];
            }
        }

        DSU dsu(n + 1);
        for (int i = 0; i < n; i++) {
            if (!dsu.merge(edges[i][0], edges[i][1])) {
                return edges[i];
            }
        }
        return {};
    }
};