Cod sursa(job #272615)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 7 martie 2009 15:24:44
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include<stdio.h>
struct Nod {
    int x;
    Nod *next;
};
int x1;
int y1;
Nod *a[100001];
int k;
int viz[100001];
int n;
int contor;
int tc;
int sir[100001];
int m;
int lista[100001];
int where0[100001];
int sirafis[100001];
int mex[100001];
void insert(Nod *&u, int val)
{
    Nod *k = new Nod;
    k -> x = val;
    k -> next = u;
    u = k;
}
void dfs(int s)
{

    viz[s] = 1;
    for(Nod *it = a[s]; it != NULL; it = it -> next)
      if (!viz[it->x])
       dfs(it->x);

    lista[++lista[0]] = s;

}
void SGnumbers()
{

    for(int i = 1; i <= lista[0]; i++)
    {
     int min = 0;
     for(Nod *it = a[lista[i]]; it; it = it -> next)
      {
          viz[mex[it->x]] = 1;
          if (!mex[it->x]) where0[lista[i]] = it -> x;
          while (viz[min] == 1) min++;

      }
     for(Nod *it = a[lista[i]]; it; it = it -> next)
      viz[mex[it->x]] = 0;
     mex[lista[i]] = min;
    }

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

    scanf("%d %d %d",&tc,&n, &m);

    for(int i = 1; i <= m; i++)
     {
         scanf("%d %d",&x1,&y1);
         insert(a[x1], y1);
     }
    for(int i = 1; i <= n; i++)
     if (!viz[i])
      dfs(i);
    for(int i = 1; i <= n; i++)
     viz[i] = 0;
    SGnumbers();
    while (tc)
    {
        scanf("%d",&k);
        int fumeanu = 1;
        for(int i = 1; i <= k; i++)
        {
         scanf("%d",&sir[i]);
         if (mex[sir[i]] != 0) fumeanu = 0;
        }
        contor = 0;
        if (fumeanu) printf("Fumeanu\n");
                     else
                     {
                         printf("Nargy\n");
                         for(int i = 1; i <= k; i++)
                          if (mex[sir[i]])
                           {
                               sirafis[++contor] = sir[i];
                               sirafis[++contor] = where0[sir[i]];
                           }
                         printf("%d ", contor/2);
                         for(int i = 1; i <= contor; i++)
                          printf("%d ", sirafis[i]);
                         printf("\n");


                     }

        tc--;


    }

}