Cod sursa(job #547011)

Utilizator savimSerban Andrei Stan savim Data 5 martie 2011 19:26:22
Problema Pioni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define MAX_N 20010
#define MAX_K 30010

int T, n, m;
int win[MAX_N], move[MAX_N], Q[MAX_N], degree[MAX_N];
int ask[MAX_K];

vector <int> G[MAX_N];

void solve() {
	for (int i = 1; i <= n; i++)
		if (degree[i] == 0)
			Q[++Q[0]] = i;

	int left = 0, right = 1;
	while (left < right) {
    	left++;

		int vertex = Q[left];

		for (vector <int>::iterator it = G[vertex].begin(); it != G[vertex].end(); ++it) {
			if (win[vertex] == 0) {
            	win[*it] = 1;
            	move[*it] = vertex;
			}

			degree[*it]--;
        	if (degree[*it] == 0) 
            	Q[++Q[0]] = *it;
		}
	}
}

void write() {
	for (int i = 1; i <= T; i++) {
    	scanf("%d", &ask[0]);
		for (int j = 1; j <= ask[0]; j++)
			scanf("%d", &ask[j]);

		int winning_strategy = 0;
		for (int j = 1; j <= ask[0]; j++)
			if (win[ask[j]])
				winning_strategy++;

		if (winning_strategy == 0)
			printf("Fumeanu\n");
		else {
        	printf("Nargy\n");
		
			printf("%d ", winning_strategy);
			for (int j = 1; j <= ask[0]; j++)
				if (win[ask[j]])
					printf("%d %d ", ask[j], move[ask[j]]);
			printf("\n");
		}
	}
}

int main() {

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

	scanf("%d %d %d", &T, &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d %d", &x, &y); 
		G[y].push_back(x);
		degree[x]++;
	}

	solve();

	write();

	return 0;
}