Cod sursa(job #134414)

Utilizator andrei_infoMirestean Andrei andrei_info Data 11 februarie 2008 18:06:04
Problema Pioni Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 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;

void df(int nod)
{
    set < int > s;

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

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

}


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

    scanf("%d %d %d\n", &T, &N, &M);
    for ( ; M>0; M--)
    {
        int a,b;
        scanf("%d %d\n", &a, &b);
        G[a].push_back(b);
        in_deg[b]++;
    };
    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;
}