Cod sursa(job #175608)

Utilizator tm_raduToma Radu tm_radu Data 10 aprilie 2008 10:00:50
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>
#define NM 20001

int n, m, t;
int w[NM], i, j, k;
int cnt, move[NM], pos[NM];
typedef struct nod {
    int vf;
    nod* urm;
} NOD, *PNOD;
PNOD l[NM];

void Add(int i, int j);
int Solve(int nod);

int main()
{
    freopen("pioni.in", "r", stdin);
    freopen("pioni.out", "w", stdout);
    scanf("%d %d %d", &t, &n, &m);
    for ( k = 1; k <= m; k++ )    
        scanf("%d %d", &i, &j),
        Add(i, j);
    for ( i = 1; i <= n; w[i] = -1, i++ );
    for ( i = 1; i <= n; i++ )
        if ( w[i] == -1 ) 
            Solve(i);
    while ( t )
    {
        t--;
        scanf("%d", &k);    
        cnt = 0;
        for ( i = 1; i <= k; i++ )
            scanf("%d", &pos[i]),
            cnt += w[pos[i]];  
        if ( cnt )
        {
            printf("Nargy\n%d", cnt);
            for ( i = 1; i <= k; i++ )
                if ( w[pos[i]] )
                    printf(" %d %d", pos[i], move[pos[i]]);
            printf("\n");
        }
        else printf ("Fumeanu\n");
    }
    return 0;
}

void Add(int i, int j)
{
    PNOD q = new NOD;
    q->vf = j;
    q->urm = l[i];
    l[i] = q;
}

int Solve(int nod)
{
    if ( w[nod] != -1 ) return w[nod];
    w[nod] = 0;
    for ( PNOD q = l[nod]; q; q = q->urm )
        if ( !Solve(q->vf) ) 
        {
            w[nod] = 1, move[nod] = q->vf;
            return 1;
        }
    return 0;
}