Cod sursa(job #175271)

Utilizator vlad.maneaVlad Manea vlad.manea Data 9 aprilie 2008 19:55:13
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
using namespace std;

#include <vector>
#include <stdio.h>
#define nmax 20005

int T, N, M, K;

int viz[nmax], winner[nmax], sol[nmax<<1];

vector<int> V[nmax];

void dfs(int n)
{
  vector<int>::iterator it;

  int los = 0;

  viz[n] = 1;

  for (it = V[n].begin(); it != V[n].end(); ++it)
  {
    if (!viz[*it])
      dfs(*it);

    if (winner[*it] == 0)
      los++;
  }

  if (los == 0)
    winner[n] = 0;
  else
    winner[n] = 1;
}

int main()
{
  int i, los, x, y;

  vector<int>::iterator j;

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

  scanf("%d", &T);

  scanf("%d%d", &N, &M);

  for (i = 1; i <= M; ++i)
  {
    scanf("%d%d", &x, &y);
    V[x].push_back(y);
  }

  // stabilesc pentru fiecare nod daca el este unul castigator sau pierzator
  for (i = 1; i <= N; ++i)
    if (!viz[i])
      dfs(i);

  while (T--)
  {
    scanf("%d", &K);

    for (los = sol[0] = 0, i = 1; i <= K; ++i)
    {
      scanf("%d", &x);

      if (winner[x] == 0)
        los++;
      else
      {
        sol[++sol[0]] = x;
        for (j = V[x].begin(); j != V[x].end(); ++j)
          if (winner[*j] == 0)
          {
            sol[++sol[0]] = *j;
            break;
          }
      }
    }

    if (sol[0])
    {
      printf("Nargy\n%d ", sol[0]>>1);

      for (i = 1; i < sol[0]; ++i)
        printf("%d ", sol[i]);

      printf("%d\n", sol[i]);
    }
    else
      printf("Fumeanu\n");
  }

  return 0;
}