Cod sursa(job #134170)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 10 februarie 2008 20:12:41
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 20004;

#define PB push_back
#define MP make_pair
#define x first
#define y second

typedef pair <int, int> PII;

int T, N, M, K;
vector <int> G[NMAX], W;
bool V[NMAX], S[NMAX];
vector <PII> R;

void read(void) {
	int i, u, v;

	scanf(" %d", &T);

	scanf(" %d %d", &N, &M);

	for (i = 0; i < M; ++i) {
		scanf(" %d %d", &u, &v);
		G[u].PB(v);
	}
}

bool DFS(int k) {
	if (V[k])
		return S[k];
	
	V[k] = true;

	vector <int> :: iterator p;

	for (p = G[k].begin(); p != G[k].end(); ++p)
		if (DFS(*p) == false)
			S[k] = true;
	
	return S[k];
}

void states(void) {
	int i;

	for (i = 1; i <= N; ++i)
		DFS(i);
}

void write(void) {
	vector <int> :: iterator p;
	vector <PII> :: iterator r;
	int i, j, u;
	bool st;

	for (i = 0; i < T; ++i) {
		scanf(" %d", &K);

		W.resize(K); st = false;
		for (j = 0; j < K; ++j) {
			scanf(" %d", &W[j]);
			st |= S[W[j]];
		}

		if (st == false) {
			printf("Fumeanu\n");
		} else {
			printf("Nargy\n");
			R.clear();

			for (j = 0; j < K; ++j) {
				u = W[j];
				if (S[u] == false) continue;
				for (p = G[u].begin(); p != G[u].end(); ++p)
					if (S[*p] == false) {
						R.PB(MP(u, *p));
						break;
					}
			}

			printf("%u ", R.size());
			for (r = R.begin(); r != R.end(); ++r)
				printf("%d %d ", r->x, r->y);
			printf("\n");
		}
	}
}

int main(void) {
	freopen("pioni.in", "rt", stdin);
	freopen("pioni.out", "wt", stdout);

	read();

	states();

	write();

	return 0;
}