Cod sursa(job #1003418)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 30 septembrie 2013 17:58:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int NMAX = 100003;

vector <int> G[NMAX], R[NMAX];
stack <int> S;
int cnt, downlink[NMAX], order[NMAX], s;

void tarjan (const int &node) {

    vector <int> :: iterator i;
    S.push (node);
    downlink[node] = ++cnt;
    order[node] = cnt;
    for (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 (order[node] == downlink[node]) {
        ++s;
        int cnode = S.top ();
        S.pop ();
        while (cnode != node)
            R[s].push_back (cnode),
            order[cnode] = -1,
            cnode = S.top (),
            S.pop ();
        R[s].push_back (node);
        order[node] = -1;
    }

}

int main () {

    freopen ("ctc.in", "r", stdin);
    freopen ("ctc.out", "w", stdout);
    int N, M, a, b, i;
    vector <int> :: iterator j;
    scanf ("%d%d", &N, &M);
    for (i = 1; i <= M; ++i)
        scanf ("%d%d", &a, &b),
        G[a].push_back (b);
    for (i = 1; i <= N; ++i)
        if (!order[i])
            tarjan (i);
    printf ("%d", s);
    for (i = 1; i <= s; ++i) {
        printf ("\n");
        for (j = R[i].begin (); j != R[i].end (); ++j)
            printf ("%d ", *j);
    }

}