Cod sursa(job #528875)

Utilizator AndreyPAndrei Poenaru AndreyP Data 3 februarie 2011 17:17:01
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;
#define N 20010
#define K 30010
#define pb push_back
inline int minim(int &x,int &y) {
	return ( (x<y) ? x : y );
}
inline int maxim(int &x,int &y) {
	return ( (x>y ) ? x : y );
}

int n,m;
vector< int > a[N];
int v[N];
int deg[N];
bitset< N > sg;
int unde[N];
int b[K];

inline void citire() {
	int x,y;

	for(int i=0; i<m; ++i) {
		scanf("%d%d",&x,&y);
                ++deg[y];
		a[x].pb(y);
	}
}

inline void precalc() {
	v[0] = 0;
	for(int i=1; i<=n; ++i) {
		if(deg[i]==0)
			v[++v[0]] = i;
	}

	int nod,nod1;
	for(int i=1; i<=v[0]; ++i) {
		nod = v[i];

		for(size_t j=0,lim=a[nod].size(); j<lim; ++j) {
			nod1 = a[nod][j];
			--deg[nod1];
			if(deg[nod1]==0) {
				v[++v[0]] = nod1;
			}
		}
	}

	if(v[0]!=n)
		exit(4);

        for(int i=n; i>0; --i) {
		nod = v[i];
		if(a[nod].empty())
			continue;

		for(size_t j=0,lim=a[nod].size(); j<lim; ++j) {
			nod1 = a[nod][j];
			if(sg[nod1]==0) {
                        	sg[nod] = 1;
				unde[nod] = nod1;
				break;
			}
		}
	}
}

inline void rezolva(int T) {
	int k,k1;

	for(; T>0; --T) {
		scanf("%d",&k);

		k1 = 0;
		for(int i=0; i<k; ++i) {
			scanf("%d",&b[i]);
			if(sg[b[i]])
				++k1;
		}

		if(k1!=0) {
			fputs("Nargy\n",stdout);
			printf("%d",k1);
			for(int i=0; i<k; ++i) {
				if(sg[b[i]])
					printf(" %d %d",b[i],unde[b[i]]);
			}
			printf("\n");
		}
		else
			fputs("Fumeanu\n",stdout);
	}
}

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

	int T;
	scanf("%d%d%d",&T,&n,&m);
	citire();
	precalc();
	rezolva(T);

	return 0;
}