Cod sursa(job #172517)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 6 aprilie 2008 15:53:58
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define maxn 20010
#define maxm 30010

int n,m,l,sol;
vector <int> a[maxn],t[maxn];
int g[maxn],gt[maxn];
int s[maxm],cost[maxn];
int c[maxn],G[maxn];
int move[maxn];

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

	int T,i,j,x,y;

	scanf("%d %d %d ",&T,&n,&m);

	for (i=1;i<=m;i++)
	{
		scanf("%d %d ",&x,&y);
		a[x].push_back(y);
		t[y].push_back(x);
	}

	for (i=1;i<=n;i++) 
	{
		gt[i] = t[i].size();
		cost[i] = g[i] = a[i].size();
	}

	for (i=1;i<=n;i++) 
		if (g[i] == 0) s[++l] = i;

	for (i=1;i<=l;i++)
	{
		for (j=0;j<g[s[i]];j++) c[G[a[s[i]][j]]] = i;

		for (j=0;j<n;j++) 
			if (c[j] != i)
			{
				G[s[i]] = j;
				break;
			}

		for (j=0;j<gt[s[i]];j++)
		{
			cost[t[s[i]][j]]--;
			if (!cost[t[s[i]][j]]) s[++l] = t[s[i]][j];
		}
	}

	for (i=1;i<=n;i++)
		if (G[i] != 0)
			for (j=0;j<g[i];j++)
				if (G[a[i][j]] == 0) move[i] = a[i][j];

	while (T)
	{
		scanf("%d ",&l);

		sol = 0;

		for (i=1;i<=l;i++) 
		{
			scanf("%d ",&s[i]);
			if (G[s[i]]) sol++;
		}

		if (sol)
		{
			printf("Nargy\n");
			printf("%d ",sol);

			for (i=1;i<=l;i++)
				if (G[s[i]]) printf("%d %d ",s[i],move[s[i]]);

			printf("\n");
		}
		else printf("Fumeanu\n");

		T--;
	}

	return 0;
}