POJ 1904 King's Quest 強連通分量 好題

題目：http://poj.org/problem?id=1904

題意：一個國王有n個王子，同時有n個女孩。每個王子都有自己喜歡的若幹個女孩，現給定一個合法的完備比對（也就是一個王子娶其中一個自己喜歡女孩），求每個王子可以選擇哪些女孩可以讓剩下的每個王子依舊能夠選擇到自己喜歡的一個女孩。

思路：這道題并不會啊，我還以為是二分圖比對，居然用強連通分量去做。如果王子u喜歡妹子v，則建一條邊u指向v，對于給出的初始完美比對，如果王子u和妹子v結婚，則建一條邊v指向u，然後求強連通分量。每一個強連通分量内的王子妹子數目必然相等，而且都可以完美比對。

總結：狀态很懵逼，部落格就随意寫寫了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int N = 4010;
struct edge
{
    int to, next;
} G[N*100];
int dfn[N], low[N], scc[N], st[N];
int head[N];
int index, cnt, num, top;
bool vis[N];
int n;
void init()
{
    memset(head, -1, sizeof head);
    memset(dfn, -1, sizeof dfn);
    memset(vis, 0, sizeof vis);
    index = cnt = num = top = 0;
}
void add_edge(int v, int u)
{
    G[cnt].to = u;
    G[cnt].next = head[v];
    head[v] = cnt++;
}
void tarjan(int v)
{
    dfn[v] = low[v] = index++;
    vis[v] = true;
    st[top++] = v;
    int u;
    for(int i = head[v]; i != -1; i = G[i].next)
    {
        u = G[i].to;
        if(dfn[u] == -1)
        {
            tarjan(u);
            low[v] = min(low[v], low[u]);
        }
        else if(vis[u])
            low[v] = min(low[v], dfn[u]);
    }
    if(dfn[v] == low[v])
    {
        num++;
        do
        {
            u = st[--top];
            vis[u] = false;
            scc[u] = num;
        }
        while(u != v);
    }
}
void slove()
{
    for(int i = 1; i <= n; i++)
        if(dfn[i] == -1)
            tarjan(i);

    int res[N];
    for(int i = 1; i <= n; i++)
    {
        int k = 0;
        for(int j = head[i]; j != -1; j = G[j].next)
            if(scc[i] == scc[G[j].to])
                res[k++] = G[j].to - n;
        sort(res, res + k);
        printf("%d", k);
        for(int j = 0; j < k; j++)
            printf(" %d", res[j]);
        printf("\n");
    }
}
int main()
{
    int m, a;
    while(~ scanf("%d", &n))
    {
        init();
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &m);
            for(int j = 0; j < m; j++)
            {
                scanf("%d", &a);
                add_edge(i, n + a);
            }
        }
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a);
            add_edge(n + a, i);
        }
        slove();
    }

    return 0;
}