题意

有n个女生和n个男生,给定一些关系表示男生喜欢女生(即两个人可以结婚),再给定一个初始匹配,表示这个男生和哪个女生结婚,初始匹配必定是合法的.求每个男生可以和哪几个女生可以结婚且能与所有人不发生冲突。

思路

好题啊。。。没想到强连通分量还能应用到完美匹配上。。。

将男生从1到n编号,女生从(n+1)到2*n编号,输入时如果男生u可以和女生v结婚,那么就做一条从u到v的边(u,v),对于输入的初始匹配(u,v)(表示男生u和女生v结婚),那么从v做一条到u的边(v,u),然后求解改图的强连通分量,如果男生和他喜欢的女生在同一个强连通分量内,则他们可以结婚（匹配）

为什么呢？因为如果这个男生找另一个女生结婚，则因为在同一个强连通分量中，则这个女生到男生原配存在路径，那么这样原配一定存在别的某个男生可以和她结婚。

抽象一下，求所有可行的完美匹配边：

①按原图建立无向边形成二分图。

②求出任意一个完美匹配。

③建立新图，原图改为有向边<i, j>，并且对于每一个完美匹配(i, j)，连一条<j, i>的边。

④求强连通分量，如果原图某条边<i, j>两点在同一个强连通分量，则该边可以是完美匹配边。

代码

using namespace std;

const int MAXN = 4005;

const int MAXM = 205005;

struct SCC{

    int scc_num, scc[MAXN];         //强连通分量总数、每个节点所属的强连通分量

    vector  scc_node[MAXN];    //强连通分量中的节点

    stack  st;

    int dfn[MAXN], low[MAXN], id;

    bool vis[MAXN], instack[MAXN];

    int cnt, head[MAXN];
struct node{

        int u, v;

        int next;

    }arc[MAXM];
void init(){

        cnt = 0;

        mem(head, -1);

        return ;

    }

    void add(int u, int v){

        arc[cnt].u = u;

        arc[cnt].v = v;

        arc[cnt].next = head[u];

        head[u] = cnt ++;

    }

    void dfs(int u){

        vis[u] = instack[u] = 1;

        st.push(u);

        dfn[u] = low[u] = ++ id;

        for (int i = head[u]; i != -1; i = arc[i].next){

            int v = arc[i].v;

            if (!vis[v]){

                dfs(v);

                low[u] = min(low[u], low[v]);

            }

            else if (instack[v]){

                low[u] = min(low[u], dfn[v]);

            }

        }

        if (low[u] == dfn[u]){

            ++ scc_num;

            while(st.top() != u){

                scc[st.top()] = scc_num;

                scc_node[scc_num].push_back(st.top());

                instack[st.top()] = 0;

                st.pop();

            }

            scc[st.top()] = scc_num;

            scc_node[scc_num].push_back(st.top());

            instack[st.top()] = 0;

            st.pop();

        }

        return ;

    }

    void tarjan(int n){

        mem(vis, 0);

        mem(instack, 0);

        mem(dfn, 0);

        mem(low, 0);

        mem(scc, 0);

        id = scc_num = 0;

        for (int i = 0; i  girl;

void solve(int n){

    S.tarjan(n+n);

    for (int i = 1; i  n && like[i][node - n]){

                girl.push_back(node - n);

            }

        }

        sort(girl.begin(), girl.end());

        printf("%d", girl.size());

        for (int j = 0; j