Cod sursa(job #175619)

Utilizator cretuMusina Rares cretu Data 10 aprilie 2008 10:46:18
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <vector>
#define MAX 20001

using namespace std;

vector<vector<int> > a;
int n, win[MAX], sol[2*MAX];

bool DF(int nod)
{
	if (win[nod] != -1) 
		if (win[nod]) return 1;
		else          return 0;
	
	int i, x;
	
	win[nod] = 0;
	x = a[nod].size();

	for (i = 0; i < x; i++)
		if (!DF(a[nod][i])) 
		{
			win[nod] = a[nod][i];
			return 1;
		}
	return 0;				
}

int main()
{
	int m, T, i, v1, v2, k;	
	ifstream fin("pioni.in");
	ofstream fout("pioni.out");

	fin >> T >> n >> m;

	a.resize(n+1);

	for (i = 1; i <= m; i++)
	{
		fin >> v1 >> v2;
		a[v1].push_back(v2);
	}			
	
	memset(win, -1, sizeof(win));

	for (i = 1; i <= n; i++)
		if (win[i] == -1)
			DF(i);
	
	int x, aux;

	for (; T; T--)	
	{
		fin >> k;
		
		x = 0;
		for (; k; k--)
		{
			fin >> aux;
			if (win[aux])
			{
				sol[++x] = aux;
				sol[++x] = win[aux];
			}
		}
		
		if (x) 
		{
			fout << "Nargy\n" << x/2 << " ";
			for (i = 1; i <= x; i++)
				fout << sol[i] << " ";
			fout << "\n";
		}
		else fout << "Fumeanu\n";
	}
				
	fin.close();
	fout.close();

	return 0;
}