题目描述

曾经有一个国王，他有 N 个儿子。

王国中有着 N 个漂亮的姑娘，每个王子也都有自己喜欢的对象。

每个王子喜欢的对象可能不止一个。

因为王子们都到了结婚的年纪，所以国王想让王子们娶了这 N 个姑娘，当然每个姑娘只能嫁给一名王子。

国王请巫师为他做一个统计，他想看看儿子们都有哪些喜欢的姑娘。

就这样，巫师制作了一个清单，上面具体列出了每一个王子喜欢哪些姑娘，并给出了一套初步的配对方案。

国王看了看巫师给他列出的清单，说道：“你总结的不错，但是我并不完全满意。我希望你列出每个王子可以婚配的女子清单，可以满足每个王子对应的清单上都是他喜欢的姑娘，并且任何一个王子从自己的清单上任意选择一名姑娘作为自己的结婚对象之后，剩下的王子仍然能够从自己的清单中选择的到自己喜欢的对象，使得所有的王子都能完成和自己喜欢的姑娘配对。”

请你帮助巫师列出国王满意的清单。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含多个整数，描述了一个王子喜欢的姑娘的清单，每行的第一个整数 K ，表示王子喜欢的姑娘的数量，接下来的 K 个整数，为这 K 个姑娘的编号。

最后一行，包含 N 个整数，表示初步的配对方案，第 i 个整数表示与第 i 个王子进行配对的姑娘编号。

输出格式
输出共 N 行。

每行包含多个整数，描述一个王子可以婚配的女子清单，第一个整数 L ，表示王子可以婚配的姑娘的数量，接下来 L 个整数，为这 L 个姑娘的编号（请按升序排列）。

数据范围
1≤N≤2000,
所有 K 加起来的和不超过200000。

样例

输入样例：
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
输出样例：
2 1 2
2 1 2
1 3
1 4

C++ 代码

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 4e3 + 6;
int n, b[N], c[N], cnt, p[N][N];
vector<int> a[N], e[N], ans[N];
int dfn[N], low[N], num;
int st[N], top, ins[N];

void tarjan(int x) 
{
    dfn[x] = low[x] = ++num;
    st[++top] = x;
    ins[x] = 1;
    for (unsigned int i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (ins[y])
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        ++cnt;
        int y;
        do {
            y = st[top--];
            ins[y] = 0;
            c[y] = cnt;
        } while (x != y);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        while (k--) {
            int x;
            scanf("%d", &x);
            a[i].push_back(x);
            p[i][x] = 1;
        }
    }
    for (int i = 1; i <= n; i++)  scanf("%d", &b[i]);
    for (int x = 1; x <= n; x++)
        for (unsigned int i = 0; i < a[x].size(); i++) 
        {
            int y = a[x][i];
            if (y == b[x]) e[y+n].push_back(x);
            else e[x].push_back(y + n);
        }
    for (int i = 1; i <= n << 1; i++)
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= n; j++)
            if (b[i] == j || (p[i][j] && c[i] == c[j+n]))
                ans[i].push_back(j);
        printf("%d", (int)ans[i].size());
        for (unsigned int j = 0; j < ans[i].size(); j++)
            printf(" %d", ans[i][j]);
        puts("");
    }
    return 0;
}

作者：李商隐
链接：https://www.acwing.com/activity/content/code/content/368143/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。