Cod sursa(job #137061)

Utilizator sandyxpSanduleac Dan sandyxp Data 16 februarie 2008 20:27:43
Problema Pioni Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <iostream>
using namespace std;

#define FIN "pioni.in"
#define FOUT "pioni.out"
#define MAXN 20001
#define MAXK 30001

int t, n, m;
int grad[MAXN], Used[MAXN], list[MAXK];
struct item { int nod; item *r; } *L[MAXN];

int St[MAXN], cap;

void df(int src) {
    int nod;
    St[++cap] = src;
    while (cap) {
        for (; L[St[cap]]; L[St[cap]] = L[St[cap]] -> r) {
            nod = L[St[cap]] -> nod;
            if (!Used[nod]) {
                St[cap+1] = nod;
                Used[nod] = 1;
                break;
            } else if (grad[nod] == 0) grad[St[cap]] = nod;
        }
        if (L[St[cap]]) { ++cap; continue; }
        if (grad[St[cap]] == 0) {
            grad[St[cap-1]] = St[cap]; // St[cap] = fiul care e Fals
        }
        --cap;
    }
}

void solve()
{
    int i, nr; // nr = nr de noduri T
    while (t--) {
        scanf("%d", &m); // de fapt k dar... :-"
        memset(Used,0,sizeof(Used));
        nr = 0;
        while (m--) {
            scanf("%d", &i);
            if (grad[i]) { // vezi dak e intr-un T
                list[nr++] = i;
            }
        }
        if (nr) {
            printf("Nargy\n%d", nr);
            for (i = 0; i < nr; ++i) {
                printf(" %d %d", list[i], grad[list[i]]);
            }
            printf("\n");
        } else {
            printf("Fumeanu\n");
        }
    }
}

void citire()
{
    int i, j;
    freopen(FIN, "r", stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d %d", &t, &n, &m);
    while (m--) {
        scanf("%d %d", &i, &j);
        item *p = new item;
        *p = (item) { j, L[i] };
        L[i] = p;
        grad[j] ++;
    }
    for (i=1; i<=n; ++i) {
        if (!grad[i]) {
            item *p = new item;
            *p = (item) { i, L[0] };
            L[0] = p;
        }
    }
}

int main()
{
    citire();
    memset(grad, 0, sizeof(grad));
    df(0);
    solve();
    return 0;
}