Cod sursa(job #780811)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 21 august 2012 22:30:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int kMaxN = 100005;

vector<int> G[kMaxN], GT[kMaxN];
int N, TSort[kMaxN], V[kMaxN];
vector< vector<int> > SCC;
vector<int> C;

void DFP(const int X) {
    ++V[X];
    for(vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y)
        if (!V[*Y])
            DFP(*Y);
    TSort[++TSort[0]] = X;
}

void DFM(const int X) {
    C.push_back(X);
    --V[X];
    for (vector<int>::iterator Y = GT[X].begin(); Y != GT[X].end(); ++Y)
        if (V[*Y])
            DFM(*Y);
}

void Kosaraju() {
    for (int X = 1; X <= N; ++X)
        if (!V[X])
            DFP(X);
    reverse(TSort+1, TSort+N+1);
    for (int i = 1; i <= N; ++i) {
        int X = TSort[i];
        if (V[X]) {
            C.clear();
            DFM(X);
            SCC.push_back(C);
        }
    }
}

void Read() {
    freopen("ctc.in", "r", stdin);
    int M; scanf("%d %d", &N, &M);
    for (; M; --M) {
        int X, Y; scanf("%d %d", &X, &Y);
        G[X].push_back(Y);
        GT[Y].push_back(X);
    }
}

void Print() {
    freopen("ctc.out", "w", stdout);
    printf("%d\n", SCC.size());
    for (int i = 0; i < SCC.size(); ++i) {
        for (int j = 0; j < SCC[i].size(); ++j)
            printf("%d ", SCC[i][j]);
        printf("\n");
    }
}

int main() {
    Read();
    Kosaraju();
    Print();
    return 0;
}