Cod sursa(job #471229)

Utilizator ilincaSorescu Ilinca ilinca Data 17 iulie 2010 20:33:21
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <cstring>
#include <vector>

#define nmax 20005
#define pb push_back
#define ff first
#define ss second

using namespace std;

vector <int> g [nmax];
vector <bool> v (nmax);
int n, t;
int f0 [nmax], mex [nmax], st [nmax], deg [nmax];

void dfs (int k)
{
	int i;
	v [k]=true;
	for (i=0; i != g [k].size (); ++i)
	{
		if (!v [g [k] [i]]) 
			dfs (g [k] [i]);
	}
	st [++st [0]]=k;
}

void rez ()
{
	int i, k, c, a;
	pair <int, int> w [nmax];
	for (; t; --t)
	{
		scanf ("%d", &k);
		c=0;
		for (i=1; i <= k; ++i)
		{
			scanf ("%d", &a);
			if (mex [a] != 0) 
			w [++c]=make_pair (a, f0 [a]);
		}
		if (c == 0)
		{
			printf ("Fumeanu\n");
			continue;
		}
		printf ("Nargy\n%d ", c);
		for (i=1; i <= c; ++i) printf ("%d %d ", w [i].ff, w [i].ss);
		printf ("\n");
	}
}

int main ()
{
	freopen ("pioni.in", "r", stdin);
	freopen ("pioni.out", "w", stdout);
	int m, a, b, i, j;
	scanf ("%d%d%d", &t, &n, &m);
	for (; m; --m)
	{
		scanf ("%d%d", &a, &b);
		g [a].pb (b);
		++deg [b];
	}
	for (i=1; i <= n; ++i) if (deg [i] == 0) dfs (i);
//	for (i=1; i <= n; ++i) fprintf (stderr, "%d ", st [i]);
	for (i=1; i <= n; ++i) 
	{
		for (j=0; j != g [st [i]].size (); ++j)
			if (!mex [g [st [i]] [j]]) f0 [st [i]]=g [st [i]] [j];
		if (f0 [st [i]]) mex [st [i]]=1;
	}
	rez ();
	return 0;
}