Cod sursa(job #418891)

Utilizator hasegandaniHasegan Daniel hasegandani Data 16 martie 2010 17:28:49
Problema Pioni Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include<stdio.h>
#include<vector>

using namespace std;

#define Nmax 30005
#define inf 0x3f3f3f3f

int N,T,nr[Nmax],t[Nmax],val[Nmax];
vector <int> l[Nmax],li[Nmax];
int c[Nmax];
int s[Nmax];

void BF()
{
    int st,dr=0,nod;
    for(int i=1;i<=N;++i)
        {
        val[i]=inf;
        if (!nr[i])
            c[++dr]=i;
        }

    for(st=1;st<=dr;++st)
        {
        if (!t[c[st]] && val[c[st]]!=inf)
            t[c[st]]=val[c[st]];
        for(int i=0;i<(int)l[c[st]].size();++i)
            {
            nod=l[c[st]][i];
            nr[nod]--;
            if (t[c[st]]%2>0)
                if (val[nod])
                    val[nod]=min(val[nod],1+t[c[st]]);
                else;
            else
                {
                t[nod]=max(t[nod],1+t[c[st]]);
                val[nod]=0;
                }
            if (!nr[nod])
                c[++dr]= nod;
            }
        }
}

void solve()
{
    BF();

    int M,a,Sol,cnt;
    for(int i=1;i<=T;++i)
        {
        scanf("%d",&M);
        Sol=0; cnt=0;
        for(int j=1;j<=M;++j)
            {
            scanf("%d",&s[j]);
            Sol = max(Sol,t[s[j]]);
            if (t[s[j]]%2==1)
                ++cnt;
            }
        if (Sol%2==1)
            {
            printf("Nargy\n");
            printf("%d ",cnt);
            for(int j=1;j<=M;++j)
                if (t[s[j]]%2==1)
                    for(int k=0,ok=0;k<(int)li[s[j]].size() && !ok;++k)
                        if (t[ li[s[j]][k] ]%2==0)
                            {
                            printf("%d %d ",s[j],li[s[j]][k]);
                            ok=1;
                            }
            printf("\n");
            }
        else
            printf("Fumeanu\n");
        }
}

void cit();

int main()
{
    cit();
    solve();
    return 0;
}

void cit()
{
    int a,b,M;
    freopen("pioni.in","r",stdin);
    freopen("pioni.out","w",stdout);
    scanf("%d%d%d",&T,&N,&M);
    for(int i=1;i<=M;++i)
        {
        scanf("%d %d\n",&a,&b);
        li[a].push_back(b);
        l[b].push_back(a);
        nr[a]++;
        }
}