Cod sursa(job #265134)

Utilizator c_sebiSebastian Crisan c_sebi Data 23 februarie 2009 13:45:17
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream.h>
#define NMAX 20001
#define KMAX 30001

int T, n, m;
int viz[NMAX], pioni[KMAX], PozCastig[NMAX];

struct nod{
	int val;
	nod *urm;
} *G[NMAX];

void add(int unde, int peCine){
	nod *p = new nod;
	p->val = peCine;
	p->urm = G[unde];
	G[unde] = p;
}

void df(int k){
	int i;
	nod *q;
	viz[k] = 1;
	for(q = G[k]; q; q=q->urm)
		if(!viz[q->val])
			df(q->val);
	for(q = G[k]; q; q=q->urm)
		if(!PozCastig[q->val]){
			PozCastig[k] = 1;
			return;
    }
	PozCastig[k] = 0;
}


int main(){
	ifstream f("pioni.in");
	ofstream g("pioni.out");
	int x, y, k, i, REZ;
	nod *q;
	f>>T>>n>>m;
	for(i = 1; i <= m; i++){
		f>>x>>y;
		add(x, y);
	}
	for(i = 1; i <= n; i++)
		if(!viz[i])
			df(i);
	while(T--){
		f>>k;
		REZ = 0;
		for(i = 0; i < k; i++){
			f >> pioni[i];
			if(PozCastig[pioni[i]]) REZ++;
		}
		if(REZ){
			g << "Nargy\n" << REZ << " ";
			for(i = 0; i < k; i++)
				if(PozCastig[pioni[i]]){
					g << pioni[i] << " ";
					for(q = G[pioni[i]]; q; q = q->urm)
						if(!PozCastig[q->val]){
							g << q->val << " ";
							break;
						}
				}
		} else g << "Fumeanu";
		g << "\n";
	}
	f.close();
	g.close();
	return 0;
}