// Fulkerson reduction: glue chains via matched edges, contract by
// pointer-jumping.

#include <iostream>
#include <vector>

void parentPointerJumping(std::vector<int>& C) {
    int n = (int)C.size();
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < n; ++i) {
            int p = C[i];
            if (C[p] != p) { C[i] = C[p]; changed = true; }
        }
    }
}

std::vector<int> parChainCoverFromMatching(const std::vector<int>& matchPartner) {
    int n = (int)matchPartner.size();
    std::vector<int> C(n);
    for (int i = 0; i < n; ++i) C[i] = i;
    for (int u = 0; u < n; ++u)
        if (matchPartner[u] != -1) C[u] = matchPartner[u];
    parentPointerJumping(C);
    return C;
}

int main() {
    // Five vertices, matched 0-2 and 1-4; vertex 3 unmatched.
    std::vector<int> match = {2, 4, 0, -1, 1};
    auto C = parChainCoverFromMatching(match);
    std::cout << "chain id:";
    for (int x : C) std::cout << ' ' << x;
    std::cout << '\n';
    return 0;
}