Cod sursa(job #418903)

Utilizator hasegandaniHasegan Daniel hasegandani Data 16 martie 2010 17:39:53
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include<stdio.h>
#include<vector>

using namespace std;

#define Nmax 20005
#define Mmax 30005
#define inf 0x3f3f3f3f

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

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,Sol,cnt,p,Min;
    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]);
            if (t[s[j]]%2==1)
                ++cnt;
            }

        if (cnt)
            {
            printf("Nargy\n");
            printf("%d ",cnt);
            for(int j=1;j<=M;++j)
                if (t[s[j]]%2==1)
                    {
                    p=0;
                    Min=inf;
                    for(int k=0;k<(int)li[s[j]].size();++k)
                        if (Min > t[li[s[j]][k]] && t[ li[s[j]][k] ]%2==0)
                            {
                            Min = t[li[s[j]][k]];
                            p = li[s[j]][k];
                            }
                    printf("%d %d ",s[j],p);
                    }
            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]++;
        }
}