Cod sursa(job #325945)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 23 iunie 2009 01:11:10
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX 20010
using namespace std;
int SG[MAX];
int def[MAX];
vector<int> v[MAX];
vector<int> spr[MAX];
int mv[MAX*3],lmv;

void move(int x){
	for (int i=0;i<v[x].size();++i) if (SG[v[x][i]]==0) { mv[++lmv]=x;mv[++lmv]=v[x][i]; return ;}
}

void gSG(int x){
	if (def[x]) return;
	def[x]=1;
	for (int i=0;i<v[x].size();++i) { gSG(v[x][i]);spr[x].push_back(SG[v[x][i]]);}
	sort(spr[x].begin(),spr[x].end());
	SG[x]=0;
	while (SG[x]<spr[x].size() && spr[x][SG[x]]==SG[x]) ++SG[x];
}

int main(void){
	freopen("pioni.in","r",stdin);
	freopen("pioni.out","w",stdout);
	int T,N,M,i,x,y,K,n,j;
	scanf("%d%d%d",&T,&N,&M);
	for (i=1;i<=M;++i){
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	for (i=1;i<=T;++i){
		scanf("%d",&K);
		n=0;lmv=0;
		for (j=1;j<=K;++j){
			scanf("%d",&x);
			gSG(x);
			if (SG[x]){
				n++;
				move(x);
			}
		}
		if (!n) { printf("Fumeanu\n");}
		else{ printf("Nargy\n");printf("%d",lmv/2);for (j=1;j<=lmv;++j) printf(" %d",mv[j]); printf("\n");}
	}
	fclose(stdout);
	return 0;
}