Cod sursa(job #1629414)

Utilizator thewildnathNathan Wildenberg thewildnath Data 4 martie 2016 15:19:38
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int NMAX = 20000;
const int KMAX = 30000;

int t, n, m, k;

int grad[1 + NMAX];
int unde[1 + NMAX];
bool bun[1 + NMAX];

int a[1 + KMAX];
int b[1 + KMAX];

vector <int> v[1 + NMAX];
vector <int> vinv[1 + NMAX];

queue <int> q;

void calc() {
  for (int i = 1; i <= n; ++i) {
    if (grad[i] == 0) {
      q.push(i);
      bun[i] = false;
    }
  }

  while (!q.empty()) {
    int nod = q.front();
    q.pop();

    for (int i = 0; i < vinv[nod].size(); ++i) {
      int dest = vinv[nod][i];

      if (!bun[nod]) {
        bun[dest] = true;
        unde[dest] = nod;
      }

      --grad[dest];
      if (grad[dest] == 0)
        q.push(dest);
    }
  }
}

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

  int x, y;

  scanf("%d%d%d", &t, &n, &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &x, &y);
    v[x].push_back(y);
    vinv[y].push_back(x);
    ++grad[x];
  }

  calc();



  while(t--) {
    int nrMut = 0;
    bool sol = false;

    scanf("%d", &k);
    for (int i = 1; i <= k; ++i) {
      scanf("%d", &x);

      if (bun[x]) {
        sol = true;
        ++nrMut;
        a[nrMut] = x;
        b[nrMut] = unde[x];
      }
    }

    if (sol) {
      printf("Nargy\n");
      printf("%d", nrMut);
      for (int i = 1; i <= nrMut; ++i)
        printf(" %d %d", a[i], b[i]);
      printf("\n");
    } else
      printf("Fumeanu\n");
  }

  return 0;
}