NC51319 King's Quest

题目：

N个男生和N个女生，告诉你每个男生喜欢的女生编号，然后给出一个初始匹配（这个初始匹配是一个完美匹配），求在保证匹配是完美匹配的基础上，输出每个男生可能会匹配的女生
在这里插入图片描述

题解：

参考题解：
让我们首先来考虑建图

如果王子u喜欢妹子v那我们可以从u向v连一条有向边

如果妹子v可以与王子u配对（即在配对表上），那我们可以从v向u连一条有向边

根据样例：

可以得到图
在这里插入图片描述
红的是王子，蓝的是妹子，绿的表示从王子到公主，黄的表示从妹子到王子

仔细观察我们发现了这张图的一些特别之处：
在这里插入图片描述
紫色部分为强连通分量
这表示在这个分量内的每个王子和这个分量内的每个妹子可以随便匹配
所以只需要枚举王子和他所在分量的妹子即可
tarjan，将同一强连通分量内的节点染色即可

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
struct edge {
    int v,nxt;
}ed[N];
stack<int> st;
int vis[N],head[N];
int low[N],dfn[N];
int cnt = 0,c2 = 0,c3 = 0;
int a[N];
vector<int> ans[N];
void add(int u,int v) {//链式前向星建边 
    cnt ++;
    ed[cnt].v = v;
    ed[cnt].nxt = head[u];
    head[u] = cnt;
}
void tarjan(int x) {//模板Tarjan算法 
    c2 ++;
    low[x] = dfn[x] = c2;
    st.push(x);//每个点进栈 
    vis[x] = 1;//表示这个点已进栈 
    for (int i = head[x];i;i = ed[i].nxt) {//遍历每条边 
        int v = ed[i].v;
        if (!dfn[v]) {//没有访问过 
            tarjan(v);
            low[x] = min(low[x],low[v]);
        }
        else if (vis[v]) {//这个点在栈里 
            low[x] = min(low[x],dfn[v]);
        }
    }
    if (low[x] == dfn[x]) {//强连通分量的根 
        c3 ++;
        int u;
        do
        {
            u=st.top() ;
            vis[u] = 0;//出栈，就去掉标记 
            a[u] = c3;//染色 
            st.pop();
        }while(x!=u);
    }
}

inline void write(int x) {//快速输出 
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
int main() {
    int n;
    scanf("%d",&n);
    for (int i = 1;i <= n;i ++ ) {
        int t;
        scanf("%d",&t);//公主个数 
        for (int j = 1;j <= t;j ++ ) {
            int x;
            scanf("%d",&x);
            add(i,x + n);
            //王子向公主连边，注意公主编号从n+1开始 
        }
    }
    for (int i = 1;i <= n;i ++ ) {
        int x;
        scanf("%d",&x);
        add(x + n,i);//反向，公主向王子连边 
    }
    for (int i = 1;i <= n * 2;i ++ ) {//两倍 
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1;i <= n;i ++ ) {
        for (int j = head[i];j;j = ed[j].nxt) {
            int v = ed[j].v;
            if (a[i] == a[v]) {
                //找既是喜欢又同色的公主，加入答案
                ans[i].push_back(v);
            }
        }
        sort(ans[i].begin(),ans[i].end());
        //一定要排序！！ 
    }
    for (int i = 1;i <= n;i ++ ) {
        write(ans[i].size());//输出个数 
        putchar(' ');
        for (int j = 0;j < ans[i].size();j ++ ) {
            write(ans[i][j] - n);//编号最后要减n 
            putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}