Cod sursa(job #1693237)

Utilizator hrazvanHarsan Razvan hrazvan Data 22 aprilie 2016 18:29:36
Problema Pioni Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <string.h>
#define MAXN 20000
#define MAXM 50000
#define MAXK 30000
int ut[MAXN], nd[MAXM], nxt[MAXM], mex[MAXN], p[MAXN], dr;
int v[MAXK], cv[MAXN], dcv;

inline void add(int x, int y){
  nd[dr] = y;
  nxt[dr] = ut[x];
  ut[x] = dr;
  dr++;
}

void calc(int x){
  if(mex[x] == -1){
    int poz = ut[x];
    char g = 0;
    while(poz != -1){
      calc(nd[poz]);
      if(mex[nd[poz]] == 1){
        g = 1;
        p[x] = nd[poz];
      }
      poz = nxt[poz];
    }
    mex[x] = !g;
  }
}

int main(){
  FILE *in = fopen("pioni.in", "r");
  int t, n, m, k, i, nrg, x, y;
  fscanf(in, "%d%d%d", &t, &n, &m);
  memset(ut, -1, sizeof ut);
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d", &x, &y);
    add(x - 1, y - 1);
  }
  memset(mex, -1, sizeof mex);
  for(i = 0; i < n; i++)
    calc(i);
  FILE *out = fopen("pioni.out", "w");
  for(; t > 0; t--){
    fscanf(in, "%d", &k);
    nrg = 0;
    for(i = 0; i < k; i++){
      fscanf(in, "%d", &v[i]);
      v[i]--;
      if(mex[v[i]] != 1)
        nrg++;
    }
    if(nrg == 0)
      fputs("Fumeanu\n", out);
    else{
      fprintf(out, "Nargy\n%d ", nrg);
      for(i = 0; i < k; i++){
        if(mex[v[i]] != 1)
          fprintf(out, "%d %d ", v[i] + 1, p[v[i]] + 1);
      }
      fputc('\n', out);
    }
  }
  fclose(out);
  return 0;
}