Cod sursa(job #471211)

Utilizator ilincaSorescu Ilinca ilinca Data 17 iulie 2010 19:31:57
Problema Pioni Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 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], deg [nmax];

void scan ()
{
	int m, a, b;
	scanf ("%d%d%d", &t, &n, &m);
	for (; m; --m)
	{
		scanf ("%d%d", &a, &b);
		g [a].pb (b);
		++deg [b];
	}
}

void dfs (int k)
{
	int i, a [nmax];
	v [k]=true;
	memset (a, 0, sizeof (a));
	for (i=0; i != g [k].size (); ++i)
	{
		if (!v [g [k] [i]]) 
			dfs (g [k] [i]);
		if (mex [g [k] [i]] == 0) f0 [k]=g [k] [i];
		a [mex [g [k] [i]]]=1;
	}
	for (i=0; a [i]; ++i);
	mex [k]=i;
}

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);
	scan ();
	for (int i=1; i <= n; ++i) if (deg [i] == 0) dfs (i);
	rez ();
	return 0;
}