对于一个有完美匹配的二分图。
1:任意找出一个完美匹配。
2:在原来的边不变的情况下。对于求出的任一个完美匹配i（左），j（右），则连接反向边j到i。
3：求强联通。
4：对于每一个联通块。
按二分图的左右分成两堆A和B。
所有在A中点i，如果和B中的点j有直接的边i到j（不是j到i）
那么i就可以和j匹配。
5：所有满足条件的就是i的所有的可能的解。
POJ 1904
有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有直接的边。则他们可以结婚。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define SIZE 4002
struct edge{int to, next;} e[300000];
int v[SIZE], instack[SIZE], dfn[SIZE], low[SIZE], cnt, top, index, sta[SIZE], belong[SIZE], num;
void insert(int from, int to)
{
    e[cnt].to = to; e[cnt].next = v[from]; v[from] = cnt++;
}
int n, k, a;
vector<int> ans[SIZE];
int len1[SIZE], len2[SIZE], l1;
void tarjan(int id)
{
    dfn[id] = low[id] = ++index;
    instack[id] = 1; sta[top++] = id;
    for(int i = v[id]; i != -1; i = e[i].next)
        if (!dfn[e[i].to])
        {
            tarjan(e[i].to);
            if (low[e[i].to] < low[id]) low[id] = low[e[i].to];
        }
        else if (instack[e[i].to] && dfn[e[i].to] < low[id])
            low[id] = dfn[e[i].to];
    if (dfn[id] == low[id])
    {
        int tmp;
        l1 = 0;
        memset(len2, 0, sizeof(len2));
        do
        {
            tmp = sta[--top]; instack[tmp] = 0;
            belong[tmp] = num;
            if (tmp > n) ans[num].push_back(tmp - n);
        }while(tmp != id);
        num++;
    }
}
bool tmp[SIZE];
int re[SIZE];
int main()
{
    while(scanf("%d", &n) != EOF)
    {
        memset(v, -1, sizeof(v)); num = cnt = index = top = 0;
        memset(dfn, 0, sizeof(dfn)); memset(instack, 0, sizeof(instack));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &k);
            while(k--)
            {
                scanf("%d", &a);
                insert(i, a + n);
            }
        }
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a);
            insert(a + n, i);
        }
        for(int i = 1; i <= n * 2; i++)
            if (!dfn[i]) tarjan(i);
        for(int i = 1; i <= n; i++)
        {
            memset(tmp, 0, sizeof(bool) * (n + 1)); int nn = 0;
            for(int j = 0; j < ans[belong[i]].size(); j++)
                tmp[ans[belong[i]][j]] = 1;
            for(int j = v[i]; j != -1; j = e[j].next)
                if (tmp[e[j].to - n]) re[nn++] = e[j].to - n;
            sort(re, re + nn);
            printf("%d", nn);
            for(int i = 0; i < nn; i++)
                printf(" %d", re[i]);
            putchar('\n');
        }
    }
    return 0;
}