Cod sursa(job #133574)

Utilizator wefgefAndrei Grigorean wefgef Data 8 februarie 2008 23:12:46
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define sz(c) int((c).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define Unique(c) sort(all(c)); (c).resize(unique(all(c)) - (c).begin())

const int Nmax = 20005;

int T, N, M;
vector<int> G[Nmax];

int SG[Nmax];
int Move[Nmax];

void ReadData() {
    freopen("pioni.in", "r", stdin);
    freopen("pioni.out", "w", stdout);
    
    scanf("%d %d %d", &T, &N, &M);
    for (int i = 0; i < M; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        G[a].pb(b);
    }
}

void DF(int k) {
    for (int i = 0; i < sz(G[k]); ++i)
        if (SG[ G[k][i] ] == -1)
            DF( G[k][i] );
            
    vector<int> v;
    for (int i = 0; i < sz(G[k]); ++i)
        v.pb(SG[ G[k][i] ]);
    Unique(v);
    v.pb(sz(v)+1);
    
    for (int i = 0; i < sz(v); ++i)
        if (v[i] != i) {
            SG[k] = i;
            return;
        }
}

void Find_SG_Values() {
    memset(SG, -1, sizeof(SG));
    for (int i = 1; i <= N; ++i)
        if (SG[i] == -1)
            DF(i);
    
    for (int i = 1; i <= N; ++i)
        if (SG[i])
            for (int j = 0; j < sz(G[i]); ++j)
                if (!SG[ G[i][j] ])
                    Move[i] = G[i][j];
}

int main() {
    ReadData();
    Find_SG_Values();
    
    for (; T; --T) {
        vector<int> ret;
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            int a;
            scanf("%d", &a);
            if (SG[a]) ret.pb(a);
        }
        
        if (sz(ret)) {
            printf("Nargy\n");
            printf("%d", sz(ret));
            for (int i = 0; i < sz(ret); ++i)
                printf(" %d %d", ret[i], Move[ret[i]]);
            printf("\n");
        }
        else
            printf("Fumeanu\n");
    }
}