Cod sursa(job #903162)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 1 martie 2013 18:51:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <cstdio>
#include <cstring>
#include <cassert>

#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>

using namespace std;

typedef long long LL;
typedef vector<int>::iterator it;

const int oo = 0x3f3f3f3f;
const int MAX_N = 100005;

vector<int> G[MAX_N], GT[MAX_N];
int N, V[MAX_N], TSort[MAX_N], SCC[MAX_N];
vector< vector<int> > Components;

void DFP(int X) {
    ++V[X];
    for (it Y = G[X].begin(); Y != G[X].end(); ++Y)
        if (V[*Y] == 0)
            DFP(*Y);
    TSort[++TSort[0]] = X;
}

void DFM(int X) {
    --V[X];
    for (it Y = GT[X].begin(); Y != GT[X].end(); ++Y)
        if (V[*Y] == 1)
            DFM(*Y);
    SCC[X] = SCC[0];
}

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

void Solve() {
    Kosaraju();
    Components = vector< vector<int> >(SCC[0], vector<int>());
    for (int X = 1; X <= N; ++X)
        Components[SCC[X] - 1].push_back(X);
}

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

void Print() {
    assert(freopen("ctc.out", "w", stdout));
    printf("%d\n", static_cast<int>(Components.size()));
    for (size_t i = 0; i < Components.size(); ++i) {
        for (it X = Components[i].begin(); X != Components[i].end(); ++X)
            printf("%d ", *X);
        printf("\n");
    }
}

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