Cod sursa(job #1025572)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 10 noiembrie 2013 11:43:26
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int T, n, m, K, Move[20100], gradint[20100], gradext[20100];
vector <int> G[20100], sol;
bool win[20100], viz[20100];
 
inline void DFS(int x)
{
	viz[x] = true;
    if(gradext[x] == 0)
    {
        win[x] = false;
        return;
    }
    vector <int>::iterator it;
    for(it = G[x].begin(); it != G[x].end(); ++it)
    {
		if(!viz[*it])
			DFS(*it);
        if(!win[*it])
		{
			win[x] = true;
			Move[x] = *it;
		}
    }
}
 
int main()
{
    int i, x, y;
	vector <int>::iterator it;
    ifstream fin("pioni.in");
    fin >> T >> n >> m;
    for( i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        G[x].push_back(y);
        gradint[y]++;
		gradext[x]++;
    }
     
    for( i = 1; i <= n; ++i)
        if(gradint[i] == 0)
            DFS(i);
         
    ofstream fout("pioni.out");
    while(T--)
    {
        fin >> K;
        while(K--)
        {
            fin >> x;
			if(win[x])
				sol.push_back(x);
        }
        if(sol.size() == 0)
            fout << "Fumeanu\n";
        else
		{
            fout << "Nargy\n";
			fout << sol.size() << ' ';
			for(it = sol.begin(); it != sol.end(); ++it)
				fout << *it << ' ' << Move[*it] << ' ';
			fout << "\n";
		}
		sol.clear();
    }
    fin.close();
    fout.close();
    return 0;
}