Cod sursa(job #403686)

Utilizator DraStiKDragos Oprica DraStiK Data 25 februarie 2010 10:30:50
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define MAX 50005
#define DIM 20005

vector <int> g[DIM];
int win[DIM],q[MAX];
int t,n,m;

void read ()
{
    int i,x,y;

    scanf ("%d%d%d",&t,&n,&m);
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d",&x,&y);
        g[x].pb (y);
    }
}

void df (int nod)
{
    vector <int> :: iterator it;

    for (it=g[nod].begin (); it!=g[nod].end (); ++it)
    {
        if (!win[*it])
            df (*it);
        if (win[*it]==2)
        {
            win[nod]=1;
            return ;
        }
    }
    win[nod]=2;
}

void solve ()
{
    vector <int> :: iterator it;
    int i,j,nr,cnt;

    for (i=1; i<=n; ++i)
        if (!win[i])
            df (i);
    for (i=1; i<=t; ++i)
    {
        cnt=0;
        scanf ("%d",&nr);
        for (j=1; j<=nr; ++j)
        {
            scanf ("%d",&q[j]);
            if (win[q[j]]==1)
                ++cnt;
        }
        if (cnt)
        {
            printf ("Nargy\n%d\n",cnt);
            for (j=1; j<=nr; ++j)
                if (win[q[j]]==1)
                    for (it=g[q[j]].begin (); it!=g[q[j]].end (); ++it)
                        if (win[*it]==2)
                        {
                            printf ("%d %d ",q[j],*it);
                            break;
                        }
            printf ("\n");
        }
        else
            printf ("Fumeanu\n");
    }
}

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

    read ();
    solve ();

    return 0;
}