题解 | 小红开宝箱

注意到 ，于是我们可以将每一个条件当作一条边建立无向图（ 可以转为 并建立自环）。目标为将每一个点匹配一条边。第一步，不断寻找度数为 的点并将其唯一邻边和此点匹配；第二步，对于剩余的点，如果度数为 ，则无解，否则此时图必然为若干个环，对于每一个环，按同一方向匹配环上的边和点即可。

维护点的度数，在度数变为 时直接处理这个点，总时间复杂度 。

#include <iostream>
#include <vector>
using namespace std;

using pii = pair<int, int>;

int n;

vector<vector<pii>> graph;
vector<bool> vise;
vector<bool> vis;
vector<int> du;
vector<int> res;

void Dfs(int x) {
    vis[x] = true;
    for (const auto& [y, v] : graph[x]) {
        if (!vise[v]) {
            vise[v] = true;
            du[x]--;
            du[y]--;
            res[v] = x;
            if (du[y] == 1) {
                Dfs(y);
            }
            return;
        }
    }
}

void Solve() {
    cin >> n;
    graph.resize(n + 1);
    du.resize(n + 1);
    res.resize(n);
    vise.resize(n);
    vis.resize(n + 1);
    for (int i = 0; i < n; i++) {
        int k, p1, p2;
        cin >> k >> p1;
        if (k == 1) {
            p2 = p1;
        } else {
            cin >> p2;
        }
        du[p1]++;
        du[p2]++;
        graph[p1].emplace_back(p2, i);
        graph[p2].emplace_back(p1, i);
    }
    for (int i = 1; i <= n; i++) {
        if (du[i] == 1 && !vis[i]) {
            Dfs(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            if (du[i] == 0) {
                cout << "kou is angry";
                return;
            }
            Dfs(i);
        }
    }
    for (const auto& x : res) {
        cout << x << ' ';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
}
// 64 位输出请用 printf("%lld")