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 ; } 
上一篇:腾讯广告联盟 Android SDK(广点通)demo的使用方式


下一篇:图的 储存 深度优先(DFS)广度优先(BFS)遍历