King's Quest - poj 1904（强连通分量+外挂输入输出）

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

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

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

#include<stdio.h>

#include<string.h>

#include<vector>

#include<algorithm>

using namespace std;

const int MAXN = ;

struct Edge{int v, next;}e[MAXN*];

int Head[MAXN], cnt;

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

int Stack[MAXN], instack[MAXN], top;

int belong[MAXN], bnt;

int N;

bool love[][];

vector< vector <int> >ans;

void InIt()

{

    ans.clear();

    ans.resize(MAXN);

    memset(love, false, sizeof(love));

    memset(dfn, false, sizeof(dfn));

    memset(Head, -, sizeof(Head));

    cnt = Index = bnt = ;

}

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!=-; 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 = , flag = ;

    char ch;

    if((ch = getchar()) == '-') flag = ;

    else if(ch >= '' && ch <= '') res = ch - '';

    while((ch = getchar()) >= '' && ch <= '')

        res = res *  + (ch - '');

    return flag ? -res : res;

}

void Out(int a) {    //输出外挂

    if(a < ) { putchar('-'); a = -a; }

    if(a >= ) Out(a / );

    putchar(a %  + '');

}

int main()

{

    while(scanf("%d", &N) != EOF)

    {

        int i, v, M;

        InIt();

        for(i=; i<=N; i++)

        {

            M = Scan();

            while(M--)

            {

                v = Scan();

                AddEdge(i, v+N);

                love[i][v] = true;

            }

        }

        for(i=; i<=N; i++)

        {

            v = Scan();

            AddEdge(v+N, i);

            love[i][v] = true;

        }

        for(i=; i<=N*; i++)

        {

            if( !dfn[i] )

                Tarjan(i);

        }

        for(i=; i<=N; i++)

        {

            v = belong[i];

            int j, len = ans[v].size();

            int a[MAXN], t=;

            for(j=; j<len; j++)

            {

                if( love[i][ ans[v][j] ] == true )

                    a[t++] = ans[v][j];

            }

            sort(a, a+t);

            printf("%d", t);

            for(j=; j<t; j++)

            {

                putchar(' ');

                Out(a[j]);

            }

            printf("\n");

        }

    }

    return ; }