Description

题目链接

题目大意：给定 $n$ 和 $n - 1$ 个点集 $E_i$，要求在每个点集中选两个点连边，问最后能否形成一棵树，并输出方案。$2 \le n \le 10^5, 2 \le \sum |E_i| \le 2 \times 10^5$。

Solution

首先我们知道，对于一棵树，除了它的根，其他点都能和连向它的祖先的那条边形成一个双射。

这提示我们做一个二分图匹配，不妨设这个二分图的左边是 $n$ 个点，右边是 $n - 1$ 个点集。

比较显然的是这个二分图的最大匹配数必须是 $n - 1$，因为每个点集都是要选一条边的。

注意到左边会有一个点不在最大匹配里，我们可以把这个点当作根，对于剩下的点，找出与其匹配的点集。

然后我们从根开始 dfs，找到当前点所在的所有点集，然后加一条当前点与对应点集匹配的点的边，直到所有点都被用完。

此时如果边的个数为 $n - 1$，则有解，否则无解。

二分图匹配的过程用 dinic 实现，时间复杂度 $O(\sqrt n m)$。

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Edge {
    int to, nxt, c;
} e[800010];

int head[200010], d[200010], cur[200010], p[200010], ansu[200010], ansv[200010];
int n, tot = 1, s, t, sum, rt, cnt;
bool vis[200010];

inline void addEdge(int u, int v, int w) {
    e[++tot] = (Edge){v, head[u], w};
    head[u] = tot;
    e[++tot] = (Edge){u, head[v], 0};
    head[v] = tot;
    return ;
}

bool bfs() {
    std::queue<int> q;
    q.push(s);
    memset(vis, false, sizeof(vis));
    memcpy(cur, head, sizeof(head));
    d[s] = 0;
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            if (e[i].c > 0 && (!vis[e[i].to])) {
                vis[e[i].to] = true;
                d[e[i].to] = d[u] + 1;
                q.push(e[i].to);
            }
        }
    }
    return vis[t];
}

int dfs(int x, int flow) {
    if (x == t)    return flow;
    int res = 0, min;
    for (int &i = cur[x]; i && flow; i = e[i].nxt) {
        if (e[i].c > 0 && d[e[i].to] == d[x] + 1) {
            min = dfs(e[i].to, std::min(flow, e[i].c));
            e[i].c -= min;
            e[i ^ 1].c += min;
            res += min;
            flow -= min;
        }
    }
    return res;
}

void dinic() {
    while (bfs())    sum += dfs(s, 2e9);
    return ;
}

void match(int x) {
    for (int i = head[x]; i; i = e[i].nxt) {
        if (e[i].to != s && (!vis[e[i].to])) {
            vis[e[i].to] = true;
            ++cnt;
            ansu[e[i].to] = x, ansv[e[i].to] = p[e[i].to];
            match(p[e[i].to]);
        }
    }
}

int main() {
    read(n);
    t = n + n;
    for (int i = 1; i <= n; ++i)    addEdge(s, i, 1);    
    for (int i = 1, c; i < n; ++i) {
        read(c);
        for (int j = 1, w; j <= c; ++j) {
            read(w);
            addEdge(w, n + i, 1);
        }
        addEdge(n + i, t, 1);
    }
    dinic();
    if (sum != n - 1) {
        puts("-1");
        return 0;
    }
    for (int i = head[s]; i; i = e[i].nxt) {
        if (e[i].c) {
            rt = e[i].to;
            break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (i == rt)    continue;
        for (int j = head[i]; j; j = e[j].nxt) {
            if ((!e[j].c) && e[j].to != s) {
                p[e[j].to] = i;
            }
        }
    }
    memset(vis, false, sizeof(vis));
    match(rt);
    if (cnt != n - 1) {
        puts("-1");
        return 0;
    }
    for (int i = n + 1; i < n + n; ++i)    printf("%d %d\n", ansu[i], ansv[i]);
    return 0;
}