Cod sursa(job #1090285)

Utilizator nytr0gennytr0gen nytr0gen Data 22 ianuarie 2014 15:51:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int Vmax = 100003;

vector<int> G[Vmax], Gt[Vmax], fin, results[Vmax];
bool use[Vmax]; int C;

void dfs(int x) {
    use[x] = 1;
    for (vector<int>::iterator it = Gt[x].begin(); it != Gt[x].end(); ++it) {
        if (use[*it] == 0) {
            dfs(*it);
        }
    }
    fin.push_back(x);
}


void dfs2(int x) {
    use[x] = 1;
    for (vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it) {
        if (use[*it] == 0) {
            dfs2(*it);
        }
    }
    results[C].push_back(x);
}

int main() {
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    int V, E, i, x, y;
    scanf("%d%d", &V, &E);
    for (i = 0; i < E; ++i) {
        scanf("%d%d", &x, &y);
        G[x] .push_back(y);
        Gt[y].push_back(x);
    }

    memset(use, false, sizeof(use));
    fin.reserve(V);
    for (i = 1; i <= V; ++i) {
        if (use[i] == 0) {
            dfs(i);
        }
    }

    memset(use, false, sizeof(use));
    C = 0;
    for (vector<int>::reverse_iterator it = fin.rbegin(); it != fin.rend(); ++it) {
        if (use[*it] == 0) {
            dfs2(*it);
            ++C;
        }
    }

    printf("%d\n", C);
    for (i = 0; i < C; ++i) {
        for (vector<int>::iterator it = results[i].begin(); it != results[i].end(); ++it) {
            printf("%d ", *it);
        }
        printf("\n");
    }

    return 0;
}