Cod sursa(job #133965)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 10 februarie 2008 08:27:34
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <vector>

using namespace std;

#define MAXN 20005
#define MAXK 30005

int N, M, K;
vector<int> con[MAXN];
int SG[MAXN], WinMV[MAXN]; char used[MAXN];

int nod[MAXK];
vector<bool> sg;

void dfs( int k )
{
	if (used[k]) return;
	used[k] = 1;
	vector<int> :: iterator it;
	for (it = con[k].begin(); it != con[k].end(); it++)
		dfs(*it);

	sg.clear(); sg.resize( con[k].size() + 1 );
	for (it = con[k].begin(); it != con[k].end(); it++)
	{
		if (SG[*it] <= (int)con[k].size())
			sg[ SG[*it] ] = 1;
		if (SG[*it] == 0)
			WinMV[k] = *it;
	}

	for (size_t i = 0; i < sg.size(); i++)
		if (!sg[i])
		{
			SG[k] = i;
			return;
		}
}

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

	int T;
	scanf("%d %d %d", &T, &N, &M);
	for (int i = 0; i < M; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		con[x].push_back(y);
	}

	for (int i = 1; i <= N; i++)
		dfs(i);

	for (; T; T--)
	{
		int Win = 0;

		scanf("%d", &K);
		for (int i = 0; i < K; i++)
		{
			scanf("%d", nod + i);
			if (SG[ nod[i] ])
				Win++;
		}

		if (!Win)
			printf("Fumeanu\n");
		else
		{
			printf("Nargy\n%d", Win);
			for (int i = 0; i < K; i++)
				if (SG[ nod[i] ])
					printf(" %d %d", nod[i], WinMV[ nod[i] ]);
			printf("\n");
		}

	}

	return 0;
}