Cod sursa(job #133882)

Utilizator MariusMarius Stroe Marius Data 9 februarie 2008 22:02:28
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const char iname[] = "pioni.in";
const char oname[] = "pioni.out";

const int MAXN = 20005;

vector <int> G[MAXN], Num(MAXN), Cnt(MAXN), deg(MAXN, 0);	int n;


void DF(int n)
{
	if (Num[n] != -1)
		return ;
	if (deg[n] == 0) {
		Num[n] = 0;
		return ;
	}
	bool zero = false;
	vector <int>::iterator i;

	for (i = G[n].begin(); i != G[n].end(); ++ i)
	{
		DF(*i);
		if (Num[*i] == 0)
			zero = true;
	}
	Num[n] = zero ? 1 : 0;
}

int main(void)
{
	FILE *fi, *fo;
	int css, cnt;

	fi = fopen(iname, "r");
	fo = fopen(oname, "w");

	fscanf(fi, "%d %d %d", &css, &n, &cnt);
	for (; cnt > 0; -- cnt)
	{
		int x, y;
		fscanf(fi, "%d %d", &x, &y);
		G[x].push_back(y);
		deg[x] ++;
	}
	for (; css > 0; -- css)
	{
		Cnt.assign(n + 1, 0);
		for (fscanf(fi, "%d", &cnt); cnt > 0; -- cnt)
		{
			int nod;
			fscanf(fi, "%d", &nod);
			Cnt[nod] ++;
		}
		Num.assign(n + 1, -1);
		for (int i = 1; i <= n; ++ i)  
			DF(i);
		int moves = 0;
		for (int i = 1; i <= n; ++ i) if (Cnt[i] && Num[i])
			moves += Cnt[i];
		if (moves)
		{
			fprintf(fo, "Nargy\n");
			fprintf(fo, "%d", moves);
			for (int i = 1; i <= n; ++ i) if (Cnt[i] && Num[i])
			{
				vector <int>::iterator j;
				for (j = G[i].begin(); j != G[i].end(); ++ j)
					if (Num[*j] == 0) 
					{
						for (; Cnt[i] > 0; -- Cnt[i])
							fprintf(fo, " %d %d", i, *j);
						break ;
					}
			}
			fprintf(fo, "\n");
		} else
			fprintf(fo, "Fumeanu\n");
	}

	fcloseall();

	return 0;
}