Cod sursa(job #297983)

Utilizator alecmanAchim Ioan Alexandru alecman Data 5 aprilie 2009 19:06:01
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define INPUT "pioni.in"
#define OUTPUT "pioni.out"
#define pb push_back

const long NMAX = 20001;
const long KMAX = 30001;

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

int T;
long N, M, K;
long Win[ NMAX ], V[ KMAX ];
bool viz[ NMAX ];
vector<long> List[ NMAX ];

void readData()
{
  long Node1, Node2;
	
  fscanf(fin, "%d %ld %ld", &T, &N, &M);
  
  for(long i = 1; i <= M; ++i)
  {
    fscanf(fin, "%ld %ld", &Node1, &Node2);
    List[ Node1 ].pb(Node2);
  }
}

void dfs(long Node)
{
  viz[ Node ] = true;
  vector<long>::iterator it;
  
  for(it = List[ Node ].begin(); it != List[ Node ].end(); ++it)
    if(!viz[ *it ]) dfs(*it);
  
  for(it = List[ Node ].begin(); it != List[ Node ].end(); ++it)
    if(!Win[ *it ] )
    { 
      Win[ Node ] = 1;
      return;
    }
    
  Win[ Node ] = 0;
}

void solve()
{
  long cont = 0;
  vector<long>::iterator it;
	
  for(long i = 1; i <= N; ++i)
    if(!viz[ i ]) dfs(i);
  
  for(;T--;)
  {
    fscanf(fin, "%ld", &K);
    cont = 0;
    
    for(long i = 1; i <= K; ++i)
    {
      fscanf(fin, "%ld", &V[ i ]);
      if(Win[ V[ i ] ]) ++cont;
    }
    
    if(cont)
    {
      fprintf(fout, "Nargy\n%ld ", cont);
      
      for(long i = 1; i <= K; ++i)
        if(Win[ V[ i ] ])
        {
          fprintf(fout, "%ld ", V[ i ]);
          for(it = List[ V[ i ] ].begin(); it != List[ V[ i ] ].end(); ++it)
            if(!Win[ *it ])
            {
              fprintf(fout, "%ld ", *it);
              break;
			}
		}
	  fprintf(fout, "\n");
	}
	else fprintf(fout, "Fumeanu\n");
  }
}

int main()
{
  readData();
  
  solve();
	
  fclose(fin);
  fclose(fout);
  
  return 0;
}