Cod sursa(job #1003401)

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

const int NMAX = 100003;

vector <int> G[NMAX], Gt[NMAX], R[NMAX];
stack <int> S;
bitset <NMAX> viz;
int s;

void topological_sort (const int &node) {

    vector <int> :: iterator i;
    viz[node] = 1;
    for (i = G[node].begin (); i != G[node].end (); ++i)
        if (!viz[*i])
            topological_sort (*i);
    S.push (node);

}

void DFST (const int &node) {

    vector <int> :: iterator i;
    viz[node] = 0;
    R[s].push_back (node);
    for (i = Gt[node].begin (); i != Gt[node].end (); ++i)
        if (viz[*i])
            DFST (*i);

}

int main () {

    freopen ("ctc.in", "r", stdin);
    freopen ("ctc.out", "w", stdout);
    int N, M, i, a, b;
    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),
        Gt[b].push_back (a);
    for (i = 1; i <= N; ++i)
        if (!viz[i])
            topological_sort (i);
    while (!S.empty ()) {
        a = S.top ();
        S.pop ();
        if (viz[a])
            ++s,
            DFST (a);
    }
    printf ("%d\n", s);
    for (i = 1; i <= s; ++i) {
        for (j = R[i].begin (); j != R[i].end (); ++j)
            printf ("%d ", *j);
        printf ("\n");
    }

}