Cod sursa(job #561633)

Utilizator CezarMocanCezar Mocan CezarMocan Data 20 martie 2011 22:01:10
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int maxN = 20100;

int T, N, M, K;
vector <int> G[maxN], GT[maxN];
int state[maxN], deg[maxN], soulMate[maxN];
int Q[maxN], p, u;
bool viz[maxN];

inline void createStates() {
    int i, j, nod, fiu;
    
    p = 1; u = 0;

    for (i = 1; i <= N; i++) {
        if (deg[i] == 0) {
            Q[++u] = i;
            viz[i] = 1;
        }
    }

    while (p <= u) {
        nod = Q[p];
        for (i = 0; i < GT[nod].size(); i++) {
            fiu = GT[nod][i];
            if (viz[fiu])   continue;

            deg[fiu]--;
            if (state[nod] == 0) {
                state[fiu] = 1;
                soulMate[fiu] = nod;
            }

            if (deg[fiu] == 0) 
                Q[++u] = fiu;
        }
        p++;
    }
}

int main() {
    int i, j, a, b;

    freopen("pioni.in", "r", stdin);
    freopen("pioni.out", "w", stdout);

    scanf("%d%d%d", &T, &N, &M);

    for (i = 1; i <= M; i++) {
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
        GT[b].push_back(a);
        deg[a]++;
    }

    createStates();

    memset(Q, 0, sizeof(Q));

    for (; T; T--) {
        scanf("%d", &K);

        int ok = 0, nr = 0;
        for (j = 1; j <= K; j++) {
            scanf("%d", &Q[j]);
            ok = ok | state[Q[j]];
            if (state[Q[j]])
                nr++;
        }

        if (ok) {
            printf("Nargy\n");
            printf("%d ", nr);
            for (i = 1; i <= K; i++) {
                if (state[Q[i]])
                    printf("%d %d ", Q[i], soulMate[Q[i]]);
            }
            printf("\n");
        }
        else
            printf("Fumeanu\n");

    }

}