Cod sursa(job #527102)

Utilizator ooctavTuchila Octavian ooctav Data 30 ianuarie 2011 16:53:14
Problema Pioni Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"pioni.in"};
const char OUT[] = {"pioni.out"};
const int INF = 1000000005;
const int NMAX = 20005;
const int KMAX = 30005;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
//#define all(a) a, a + 

int T, N, M, K;
vector<int> Graf[NMAX], Inv[NMAX];
int out[NMAX];
bool win[NMAX];
int mut[NMAX];

void citi()
{
	scanf("%d%d%d", &T, &N, &M);
	FOR(i, 1, M)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		Graf[x].pb(y);
		Inv[y].pb(x);
		out[x]++;
	}
}

bool vecini(int nod)
{
	FORIT(it, Graf[nod])
		if(!win[*it])
		{
			mut[nod] = *it;
			return 1;
		}
	return 0;
}

void numerota()
{
	queue<int> Q;
	FOR(i, 1, M)
		if(!out[i])
			Q.push(i);
	while(!Q.empty())
	{
		int x = Q.front();
		Q.pop();
		win[x] = vecini(x);
		FORIT(it, Inv[x])
		{
			out[*it]--;
			if(!out[*it])
				Q.push(*it);
		}
	}
}

int NR;
pair<int, int> SOL[KMAX];
	
void apel()
{
	scanf("%d", &K);
	FOR(i, 1, K)
	{
		int x;
		scanf("%d", &x);
		if(win[x])
			SOL[++NR] = mp(x, mut[x]);
	}
}

void scrie()
{
	if(NR)
	{
		printf("Nargy\n");
		printf("%d ", NR);
		FOR(i, 1, NR)
			printf("%d %d ", SOL[i].fs, SOL[i].ss);
		printf("\n");
	}
	else
		printf("Fumeanu\n");
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	numerota();
	FOR(i, 1, T)
	{
		NR = 0;
		apel();
		scrie();
	}
	return 0;
}