# AGC029F Construction of a tree

Author: Fanyi Pu

Published: 2020-02-23

Canonical: <https://pufanyi.com/blog/oi-icpc/atcoder/agc029-f>

AGC029F Construction of a tree 题解。

题意大概就是给你 $n-1$ 个点集，全集是 $\{1,2,\dots, n\}$，现在要从每个点点集中抽出两个点来连边，最终形成一棵树。让你输出方案或判断无解。$n$ 有 $10^5$，所有集合大小之和不超过 $2\times 10^5$。

考虑构造，儿子向父亲连边。也就是说，每个集合最后都是儿子 $\to$ 父亲的一条边，那么我们可以随便选一个点作为跟，其余点肯定对应一个集合，表示这个集合所对应的边，一端是他，另一端是他父亲。其实也就是一个匹配，左边是除了根节点以外的所有点，右边是所有点集。点与点集有边当且仅当这个点在点集中出现。

显然地，如果这个匹配无解那么最终肯定无解，因为根本找不到一个完美的儿子 $\to$ 父亲的映射。找到匹配之后我们把根加上去，跟前面的连法一样。如果连上之后这张图仍然不连通，那么显然无解，因为两个独立的连通块显然没有生成树。

那如果上面的判掉之后是否就一定有解了呢？我们考虑构造解。我们从根节点开始 `bfs`，我们考虑根节点所有连出去的集合，这些集合的匹配点的父亲都定作是这个根，然后这样递归下去。不难发现，这样做是肯定有解的。

考虑复杂度，边数 $m$ 是集合的总大小，用 `Dinic` 做二分图匹配，复杂度 $\mathcal{O}(m\sqrt{n})$，之后的构造解复杂度 $\mathcal{O}(m)$，所以总复杂度 $\mathcal{O}(m\sqrt{n})$。

[代码](https://atcoder.jp/contests/agc029/submissions/10301461)

```cpp
#define _CRT_SECURE_NO_WARNINGS

#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

inline char gc() {
    static const int L = 233333;
    static char sxd[L], *sss = sxd, *ttt = sxd;
    if (sss == ttt) {
        ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
        if (sss == ttt) {
            return EOF;
        }
    }
    return *sss++;
}

#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
    char dd;
    for (; !isalpha(c); dd);
    return c;
}

inline char readchar() {
    char dd;
    for (; c == ' '; dd);
    return c;
}

template <class T>
inline bool read(T& x) {
    bool flg = false;
    char dd;
    x = 0;
    for (; !isdigit(c); dd) {
        if (c == '-') {
            flg = true;
        } else if(c == EOF) {
            return false;
        }
    }
    for (; isdigit(c); dd) {
        x = (x * 10) + (c ^ 48);
    }
    if (flg) {
        x = -x;
    }
    return true;
}
#undef dd

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x < 10) {
        putchar(x | 48);
        return;
    }
    write(x / 10);
    putchar((x % 10) | 48);
}

template <class T>
inline void writesp(T x) {
    write(x);
    putchar(' ');
}

template <class T>
inline void writeln(T x) {
    write(x);
    puts("");
}

#define lowbit(x) (x & -x)

namespace dfcmd {
    const int maxn = 200005;
    const int inf = 0x3f3f3f3f;

    struct Edge {
        int to, nxt, flow;
    } e[maxn * 10];

    int first[maxn];
    int first_bak[maxn];

    inline void add_edge(int from, int to) {
        static int cnt = -1;
        e[++cnt].nxt = first[from];
        first[from] = cnt;
        e[cnt].to = to;
        e[cnt].flow = 1;
        e[++cnt].nxt = first[to];
        first[to] = cnt;
        e[cnt].to = from;
        e[cnt].flow = 0;
    }

    int n, nn, S, T;
    vector<int> dian[maxn];
    vector<int> too[maxn];

    int dep[maxn];

    inline bool bfs() {
        for (int i = 1; i <= n << 1; ++i) {
            first[i] = first_bak[i];
        }
        queue<int> q;
        memset(dep, 0, sizeof(dep));
        dep[S] = 1;
        q.push(S);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (int i = first[now]; ~i; i = e[i].nxt) {
                int to = e[i].to;
                if (!dep[to] && e[i].flow) {
                    dep[to] = dep[now] + 1;
                    q.push(to);
                }
            }
        }
        return dep[T];
    }

    inline int dfs(int now, int all) {
        if (now == T) {
            return all;
        }
        int flow = 0;
        for (int i = first[now]; ~i; i = e[i].nxt) {
            first[now] = i;
            int to = e[i].to, f;
            if (e[i].flow && dep[to] == dep[now] + 1 && (f = dfs(to, min(e[i].flow, all)))) {
                all -= f;
                flow += f;
                e[i].flow -= f;
                e[i ^ 1].flow += f;
            }
        }
        return flow;
    }

    inline int Dinic() {
        int ans = 0;
        while (bfs()) {
            ans += dfs(S, inf);
        }
        return ans;
    }

    int pp[maxn];
    bool viss[maxn];
    pair<int, int> ee[maxn];

    inline int getans() {
        for (int now = 1; now < n; ++now) {
            for (int i = first[now]; ~i; i = e[i].nxt) {
                int to = e[i].to;
                if (!e[i].flow) {
                    pp[now] = to;
                    pp[to] = now;
                    break;
                }
            }
        }
        queue<int> q;
        while (!q.empty()) {
            q.pop();
        }
        q.push(n);
        memset(viss, 0, sizeof(viss));
        viss[n] = true;
        int ans = 0;
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (auto jh : too[now]) {
                if (!viss[pp[jh]]) {
                    viss[pp[jh]] = true;
                    ee[jh] = make_pair(now, pp[jh]);
                    ans++;
                    q.push(pp[jh]);
                }
            }
        }
        return ans;
    }

    int Main() {
        read(n);
        memset(first, 0xff, sizeof(first));
        for (int i = 1, cnt, xx; i < n; ++i) {
            read(cnt);
            while (cnt--) {
                read(xx);
                dian[i + n - 1].push_back(xx);
                too[xx].push_back(i + n - 1);
                if (xx != n) {
                    add_edge(xx, i + n - 1);
                }
            }
        }
        nn = (n - 1) << 1;
        S = ++nn, T = ++nn;
        for (int i = 1; i < n; ++i) {
            add_edge(S, i);
        }
        for (int i = 1; i < n; ++i) {
            add_edge(i + n - 1, T);
        }
        for (int i = 1; i <= n << 1; ++i) {
            first_bak[i] = first[i];
        }
        int ff = Dinic();
        if (ff != n - 1) {
            puts("-1");
            return 0;
        }
        if (getans() != n - 1) {
            puts("-1");
            return 0;
        }
        for (int i = 1; i < n; ++i) {
            writesp(ee[i + n - 1].first), writeln(ee[i + n - 1].second);
        }
        return 0;
    }
}

int main() {
    return dfcmd::Main();
}
```