Cod sursa(job #133978)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 10 februarie 2008 10:27:08
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

const int N_MAX = 20010;

vector <int> G[N_MAX], G2[N_MAX];
int grad[N_MAX], dest[N_MAX], win[N_MAX], nrv[N_MAX];

void wl()
{
	int in = 1, sf = dest[0] + 1, nod;
	vector <int>::iterator it;

	while (in < sf) {
		nod = dest[in];
		in ++;

		for (it = G[nod].begin(); it != G[nod].end(); ++ it) {
			grad[*it] --;
			if (win[nod] == -1) win[*it] = 1;
			else {
				if (!win[*it]) win[*it] = -1;
			}

			if (grad[*it] == 0) dest[sf ++] = *it;
		}
	}
}

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

	int T, N, M, a, b, i;
	scanf("%d %d %d\n", &T, &N, &M);

	for (i = 1; i <= M; i ++) {
		scanf("%d %d\n", &a, &b);

		G[b].push_back(a);
		G2[a].push_back(b);
		grad[a] ++;
	}

	for (i = 1; i <= N; i ++) {
		if (grad[i] == 0) dest[++ dest[0]] = i;
		win[i] = -1;
	}

	wl();

	int W, K, x, j, cati;
	vector <int>::iterator it;

	for (; T; T --) {
		memset(nrv, 0, sizeof(nrv));

		scanf("%d ", &K);
		for (i = 1; i <= K; i ++) {
			scanf("%d ", &x);
			nrv[x] ++;
		}

		W = 0; cati = 0;
		for (i = 1; i <= N; i ++) {
			if (win[i] == 1 && nrv[i]) {
				W = 1;
				cati += nrv[i];
			}
		}

		if (W == 1) {
			printf("Nargy\n");
			printf("%d ", cati);

			for (i = 1; i <= N; i ++) {
				if (win[i] == 1 && nrv[i]) {
					
					for (it = G2[i].begin(); it != G2[i].end(); ++ it) {
						if (win[*it] == -1) {
							for (j = 1; j <= nrv[i]; j ++) {
								printf("%d %d ", i, *it);
							}
							break;
						}
					}
				}
			}
			printf("\n");
		} else {
			printf("Fumeanu\n");
		}
	}

	return 0;
}