problem

洛谷链接

solution

考虑 Ω = { E 1 , . . . , E n − 1 } \Omega=\{E_1,...,E_{n-1}\} Ω={E1​,...,En−1​} 的一个子集 S S S，记 f ( S ) = { u ∣ u ∈ E i ∈ S } f(S)=\{u\mid u\in E_i\in S\} f(S)={u∣u∈Ei​∈S}。

显然当 S ≠ ∅ ∧ ∣ f ( S ) ∣ ≤ ∣ S ∣ S\ne\empty\wedge\big|f(S)\big|\le |S| S​=∅∧∣∣​f(S)∣∣​≤∣S∣ 时，一定会有环存在，弄不出一棵树。

所以只有 ∣ f ( S ) ∣ ≥ ∣ S ∣ + 1 \big|f(S)\big|\ge |S|+1 ∣∣​f(S)∣∣​≥∣S∣+1 时才有解，这是必要条件。

这十分的 Hall \text{Hall} Hall 定理长相，下面二分图的构造将说明这同时也是充分条件。

左部点集有 n n n 个点 ，右部 n − 1 n-1 n−1 个点分别表示一个点集。若 u ∈ E i u\in E_i u∈Ei​，则在二分图连一条左部编号 u u u 的点到右部第 i i i 个点。

有解首先要满足右部 n − 1 n-1 n−1 个点完备匹配（每个子集都要选点）。

可以用网络流 dinic \text{dinic} dinic 跑。

这样的话左部就一定会剩下一个未匹配点，记为 r t rt rt。

从 r t rt rt 开始 dfs \text{dfs} dfs 随便找一个右部与之有边相连且还未标记过的点 i i i，再找到这个点在右部的匹配点 l i n k ( i ) link(i) link(i)。

将 i i i 打上标记，意味着 i i i 子集选择 r t , l i n k ( i ) rt,link(i) rt,link(i) 两个点。

再从 l i n k ( i ) link(i) link(i) 继续 dfs \text{dfs} dfs 下去。

在 dfs \text{dfs} dfs 的过程中，就顺便还判断了是否有解并且记录解的选择。如果所有子集都标记了则有解。

同时，不存在将有解判为无解的可能。

dfs \text{dfs} dfs 的任何时候都是左部点访问个数 = = = 右部点访问个数 + 1 +1 +1，因为只多了一个 r t rt rt。

如果到了某个左部点发现右边的所有连边子集点都被打上了标记，则剩下的左部点和右部点个数就相同了。

就出现了 ∣ f ( S ) ∣ ≤ ∣ S ∣ \big|f(S)\big|\le |S| ∣∣​f(S)∣∣​≤∣S∣ 的情况，就一定无解。

也就是说如果无解一定是出现了 ∣ f ( S ) ∣ ≤ ∣ S ∣ \big|f(S)\big|\le |S| ∣∣​f(S)∣∣​≤∣S∣ 的情况，这也说明了这个条件是充要的。

code

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 200005
struct node { int to, nxt, flow; }E[maxn << 2];
int head[maxn], cur[maxn], dep[maxn], link[maxn];
bool vis[maxn];
int cnt = -1, s, t, n;
queue < int > q;
vector < int > ans[maxn];

void addedge( int u, int v, int w ) {
    E[++ cnt] = { v, head[u], w }, head[u] = cnt;
    E[++ cnt] = { u, head[v], 0 }, head[v] = cnt;
}

bool bfs() {
    memset( dep, 0, sizeof( dep ) );
    memcpy( cur, head, sizeof( head ) );
    dep[s] = 1; q.push( s );
    while( ! q.empty() ) {
        int u = q.front(); q.pop();
        for( int i = head[u], v;~ i;i = E[i].nxt )
            if( ! dep[v = E[i].to] and E[i].flow ) 
                dep[v] = dep[u] + 1, q.push( v );
    }
    return dep[t];
}

int dfs( int u, int cap ) {
    if( ! cap or u == t ) return cap;
    int flow = 0;
    for( int i = cur[u];~ i;i = E[i].nxt ) {
        cur[u] = i; int v = E[i].to;
        if( dep[v] == dep[u] + 1 ) {
            int w = dfs( v, min( cap, E[i].flow ) );
            if( ! w ) continue;
            E[i ^ 1].flow += w;
            E[i].flow -= w;
            flow += w;
            cap -= w;
            if( ! cap ) break;
        }
    }
    return flow;
}

int dinic() {
    int ret = 0;
    while( bfs() ) ret += dfs( s, inf );
    return ret;
}

void dfs( int u ) {
    cnt ++;
    for( int i = head[u];~ i;i = E[i].nxt ) {
        int v = E[i].to;
        if( v > n and ! vis[v] ) {
            ans[v].push_back( u );
            ans[v].push_back( link[v] );
            vis[v] = 1;
            dfs( link[v] );
        }
    }
}

int main() {
    memset( head, -1, sizeof( head ) );
    scanf( "%d", &n );
    s = 0, t = n << 1;
    for( int i = 1, k, x;i < n;i ++ ) {
        scanf( "%d", &k );
        for( int j = 1;j <= k;j ++ ) {
            scanf( "%d", &x );
            addedge( x, n + i, inf );
        }
    }
    for( int i = 1;i <= n;i ++ ) addedge( s, i, 1 );
    for( int i = 1;i < n;i ++ ) addedge( i + n, t, 1 );
    if( dinic() != n - 1 ) return ! puts("-1");
    for( int i = n + 1;i < (n << 1);i ++ )
        for( int j = head[i];~ j;j = E[j].nxt )
            if( E[j].to < i and E[j].flow ) {
                link[i] = E[j].to;
                break;
            }
    int rt;
    for( int i = 1;i <= n;i ++ ) {
        for( int j = head[i];~ j;j = E[j].nxt )
            if( E[j].to > i and E[j ^ 1].flow ) goto pass;
        rt = i;
        break;
        pass :;
    }
    cnt = 0;
    dfs( rt );
    if( cnt ^ n ) return ! puts("-1");
    for( int i = n + 1;i < (n << 1);i ++ )
        printf( "%d %d\n", ans[i][0], ans[i][1] );
    return 0;
}