Cod sursa(job #1164395)

Utilizator cbanu96Banu Cristian cbanu96 Data 2 aprilie 2014 00:55:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define FILEIN "ctc.in"
#define FILEOUT "ctc.out"
#define NMAX 100005

vector<int> G[NMAX], GT[NMAX];
vector<int> Comp[NMAX];
int CompCnt;
int N, M;
vector<int> Sortare;
bool Used[NMAX];

void DFSort(int x) {
    Used[x] = 1;

    for ( int i = 0; i < G[x].size(); i++ ) {
        if (!Used[G[x][i]]) {
            DFSort(G[x][i]);
        }
    }

    Sortare.push_back(x);
}

void DFFinal(int x, int comp) {
    Used[x] = 1;

    Comp[comp].push_back(x);

    for ( int i = 0; i < GT[x].size(); i++ ) {
        if (!Used[GT[x][i]])
            DFFinal(GT[x][i], comp);
    }
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &N, &M);

    for ( int i = 1, x, y; i <= M; i++ ) {
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for ( int i = 1; i <= N; i++ ) {
        if (!Used[i])
            DFSort(i);
    }

    reverse(Sortare.begin(), Sortare.end());

    memset(Used, 0, sizeof(Used));
    for ( int i = 0; i < N; i++ ) {
        if (!Used[Sortare[i]])
            DFFinal(Sortare[i], ++CompCnt);
    }

    printf("%d\n", CompCnt);
    for ( int i = 1; i <= CompCnt; i++ ) {
        for ( int j = 0; j < Comp[i].size(); j++)
            printf("%d ", Comp[i][j]);
        printf("\n");
    }

    return 0;
}