Cod sursa(job #134425)

Utilizator andrei_infoMirestean Andrei andrei_info Data 11 februarie 2008 18:37:36
Problema Pioni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>

#define MAX 20005

using namespace std;

vector <int> G[MAX];

int nr[MAX], N,M,T, in_deg[MAX], fiu0[MAX], Q[60010], nr_Q, viz[MAX];

void df(int nod)
{
    //set < int > s;
    nr[nod] = 0;
    viz[nod] = 1;
    for ( vector< int > :: iterator it = G[nod].begin(); it!= G[nod].end(); it++)
    {
        if ( !viz[*it] )
             df(*it);
        //s.insert ( nr[*it]);
        if ( nr[*it] == 0 )
            nr[nod] = 1;

        if ( nr[*it] == 0 )
            fiu0[nod] = *it;
    };

    //int r = 0;
    //while( s.find(r) != s.end() ) r++;
    //nr[nod] = r;

}

void df2 (int nod )
{
    if ( viz[nod] )
        exit(123);
    viz[nod] = 1;
    for ( vector < int > :: iterator it = G[nod].begin(); it!= G[nod].end(); it++)
        df2(*it);
};


int main()
{
    freopen("pioni.in", "r", stdin);
    freopen("pioni.out", "w", stdout);

    scanf("%d %d %d", &T, &N, &M);
    for ( ; M>0; M--)
    {
        int a,b;
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        in_deg[b]++;
    };

    for (int i = 1; i<=N; i++)
        if ( !in_deg[i])
        {
            memset(viz, 0, sizeof(viz));
            df2(i);
        }
    memset(viz, 0, sizeof(viz));


    for (int i=1; i<=N; i++)
        if ( !in_deg[i] )
            df(i);

    for ( ; T>0; T--)
    {
        int K;
        scanf("%d", &K);
        nr_Q = 0;
        int fumy = 1;

        for (int i=0; i<K; i++)
        {
            int aux;

            scanf("%d", &aux);
            if (nr[aux] != 0 )
            {
                fumy = 0;
                Q[nr_Q] = aux;
                Q[nr_Q+1] = fiu0[aux];
                nr_Q+=2;
            }
        }
        if (fumy )
            printf("Fumeanu\n");
        else
        {
            printf("Nargy\n");
            printf("%d ", nr_Q/2);
            for (int i = 0; i<nr_Q; i++)
                printf("%d ", Q[i]);
            printf("\n");
        }

    }



    fclose(stdin);
    fclose(stdout);

    return 0;
}