King's Quest

题意：国王有N个儿子，每个儿子都有很多喜欢的姑娘，官员为每个王子都找了一个姑娘让他们结婚，不过国王不满意，他想知道他的每个儿子都可以和那个姑娘结婚（前提他的儿子必须喜欢那个姑娘）

分析：因为最下面一行已经给出来每个王子可以结婚的对象了，所以就不必在去求完备匹配了，直接加入反边求出来环就行了，不过注意环中的姑娘未必是王子喜欢的对象，需要再次判断一下才行。ps.第一次知道有输出输入外挂这东西，不过优化的确实很给力。

************************************************************************

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN = 4005;

struct Edge{int v, next;}e[MAXN*1000];
int Head[MAXN], cnt;
int dfn[MAXN], low[MAXN], Index;
int Stack[MAXN], instack[MAXN], top;
int belong[MAXN], bnt;
int N;
bool love[2005][2005];
vector< vector <int> >ans;

void InIt()
{
    ans.clear();
    ans.resize(MAXN);

    memset(love, false, sizeof(love));
    memset(dfn, false, sizeof(dfn));
    memset(Head, -1, sizeof(Head));

    cnt = Index = bnt = 0;
}
void AddEdge(int u, int v)
{
    e[cnt].v = v;
    e[cnt].next = Head[u];
    Head[u] = cnt++;
}
void Tarjan(int i)
{
    int v;

    dfn[i] = low[i] = ++Index;
    Stack[++top] = i, instack[i] = true;

    for(int j=Head[i]; j!=-1; j=e[j].next)
    {
        v = e[j].v;

        if( !dfn[v] )
        {
            Tarjan(v);
            low[i] = min(low[i], low[v]);
        }
        else if( instack[v] )
            low[i] = min(low[i], dfn[v]);
    }

    if(low[i] == dfn[i])
    {
        ++bnt;
        do
        {
            v = Stack[top--];
            instack[v] = false;
            belong[v] = bnt;
            if(v > N)
                ans[bnt].push_back(v-N);
        }
        while(i != v);
    }
}

int Scan() {    //输入外挂
    int res = 0, flag = 0;
    char ch;
    if((ch = getchar()) == '-') flag = 1;
    else if(ch >= '0' && ch <= '9') res = ch - '0';
    while((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + (ch - '0');
    return flag ? -res : res;
}

void Out(int a) {    //输出外挂
    if(a < 0) { putchar('-'); a = -a; }
    if(a >= 10) Out(a / 10);
    putchar(a % 10 + '0');
}

int main()
{
    while(scanf("%d", &N) != EOF)
    {
        int i, v, M;

        InIt();

        for(i=1; i<=N; i++)
        {
            M = Scan();

            while(M--)
            {
                v = Scan();
                AddEdge(i, v+N);
                love[i][v] = true;
            }
        }

        for(i=1; i<=N; i++)
        {
            v = Scan();
            AddEdge(v+N, i);
            love[i][v] = true;
        }

        for(i=1; i<=N*2; i++)
        {
            if( !dfn[i] )
                Tarjan(i);
        }

        for(i=1; i<=N; i++)
        {
            v = belong[i];

            int j, len = ans[v].size();
            int a[MAXN], t=0;

            for(j=0; j<len; j++)
            {
                if( love[i][ ans[v][j] ] == true )
                    a[t++] = ans[v][j];
            }

            sort(a, a+t);

            printf("%d", t);
            for(j=0; j<t; j++)
            {
                putchar(' ');
                Out(a[j]);
            }
            printf("
");
        }
    }

    return 0; 

}