Cod sursa(job #530043)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 6 februarie 2011 18:32:50
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#include <queue>
#include <vector>
#define NMAX 20005
#define LMAX 30005
#define pb push_back
using namespace std;
int t,n,m,r,deg[NMAX],C[NMAX],E[NMAX];
vector <int> A[NMAX],B[NMAX];
queue <int> Q;
struct move{int a,b;};
move D[LMAX];
void read()
{
	scanf("%d%d%d",&t,&n,&m);
	int i,x,y;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		deg[x]++;
		A[x].pb(y); 
		B[y].pb(x);
	}
}
void precompute()
{
	int i,nod,vec;
	for (i=1; i<=n; i++)
		if (deg[i]==0)
			Q.push(i);
	while (!Q.empty())
	{
		nod=Q.front();
		Q.pop();
		for (i=0; i<B[nod].size(); i++)
		{
			vec=B[nod][i];
			deg[vec]--;
			if (deg[vec]==0)
				Q.push(vec);
		}
		C[nod]=0;
		for (i=0; i<A[nod].size(); i++)
		{
			vec=A[nod][i];
			if (!C[vec])
			{
				C[nod]=1;
				break ;
			}
		}
	}
}
void solve()
{
	int i,j,x,tip,w,nod;
	for (i=1; i<=n; i++)
		if (C[i])
			for (j=0; j<A[i].size(); j++)
				if (C[A[i][j]]==0)
				{
					E[i]=A[i][j];
					break ;
				}
	for (i=1; i<=t; i++)
	{
		scanf("%d",&r);
		tip=0; w=0;
		for (j=1; j<=r; j++)
		{
			scanf("%d",&x);
			if (C[x])
			{
				tip=1;
				if (E[x])
					D[++w].a=x,D[w].b=E[x];
			}
			else
				nod=x;
		}
		if (tip)
		{
			printf("Nargy\n");
			if (w)
			{
				printf("%d ",w);
				for (j=1; j<=w; j++)
					printf("%d %d ",D[j].a,D[j].b);
				printf("\n");
			}
			else
				printf("1 %d %d\n",nod,A[nod][0]);
		}
		else
			printf("Fumeanu\n");
	}
}
int main()
{
	freopen("pioni.in","r",stdin);
	freopen("pioni.out","w",stdout);
	read();
	precompute();
	solve();
	return 0;
}