Cod sursa(job #1122418)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 25 februarie 2014 18:04:10
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;

const int NMAX = 102;

vector <short> G[NMAX], rec_s, ans;
stack <short> S;
bitset <NMAX> check;
short downlink[NMAX], order[NMAX], scc[NMAX], s, c, R;

void tarjan (const short &node) {

    order[node] = downlink[node] = ++s;
    S.push (node);
    for (vector <short> :: iterator i = G[node].begin (); i != G[node].end (); ++i)
        if (!order[*i]) {
            tarjan (*i);
            downlink[node] = min (downlink[node], downlink[*i]);
        }
        else
            if (order[*i] != -1)
                downlink[node] = min (downlink[node], downlink[*i]);
    if (downlink[node] == order[node]) {
        ++c;
        while (S.top () != node) {
            scc[S.top ()] = c;
            order[S.top ()] = -1;
            S.pop ();
        }
        scc[node] = c;
        order[node] = -1;
        S.pop ();
    }

}

void DFS () {

    check[rec_s.back ()] = 1;
    for (vector <short> :: iterator i = G[rec_s.back ()].begin (); i != G[rec_s.back ()].end (); ++i)
        if (!check[*i]) {
            if (scc[rec_s.back ()] == scc[*i]) {
                rec_s.push_back (*i);
                DFS ();
                rec_s.pop_back ();
            }
        }
        else
            if (rec_s.size () > ans.size () && rec_s[0] == *i)
                ans = rec_s;

}

int main () {

    freopen ("plimbare.in", "r", stdin);
    freopen ("plimbare.out", "w", stdout);
    short N, M, a, b, i;
    scanf ("%hd", &N);
    M = (N * (N - 1)) >> 1;
    while (M--) {
        scanf ("%hd%hd", &a, &b);
        G[a].push_back (b);
    }
    for (i = 1; i <= N; ++i)
        if (!order[i])
            tarjan (i);
    for (i = 1; i <= N; ++i) {
        rec_s.push_back (i);
        DFS ();
        rec_s.pop_back ();
        check.reset ();
    }
    printf ("%d\n", ans.size ());
    for (vector <short> :: iterator j = ans.begin (); j != ans.end (); ++j)
        printf ("%hd ", *j);

}