Cod sursa(job #906269)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 6 martie 2013 18:05:21
Problema Pioni Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <vector>

#define MAX 20005

using namespace std;

int T, N, M;
vector<int> V[MAX], sol;
bool win[MAX], viz[MAX];
int go[MAX];

int dfs(int nod) {
    if(viz[nod]) return win[nod];
    win[nod] = false, viz[nod] = true;
    for(size_t i = 0; i < V[nod].size(); i++) {
        int dest = V[nod][i];
        if(!dfs(dest)) {
            win[nod] = true;
            go[nod] = dest;
        }
    }
    return win[nod];
}

int main()
{
    ifstream in("pioni.in"); ofstream out("pioni.out");
    in>>T>>N>>M;
    for(int i = 1, A, B; i <= M; i++) {
        in>>A>>B;
        V[A].push_back(B);
    }
    for(int i = 1; i <= N; i++)
        if(!viz[i]) dfs(i);
    for(int i = 1, cnt; i <= T; i++) {
        in>>cnt; sol.clear();
        for(int j = 1, A; j <= cnt; j++) {
            in>>A;
            if(win[A]) sol.push_back(A);
        }
        if(sol.empty()) out<<"Fumeanu\n";
        else {
            out<<"Nargy\n";
            for(size_t j = 0; j < sol.size(); j++) {
                out<<sol[j]<<" "<<go[sol[j]]<<" ";
            }
            out<<"\n";
        }
    }
    in.close(); out.close();
    return 0;
}