Cod sursa(job #1361325)

Utilizator marcu.iulian13Iulian Marcu marcu.iulian13 Data 25 februarie 2015 20:43:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>

#define MAX_N 100000
#define MAX_M 200000

using namespace std;

int n, m;
vector<int> G[MAX_N];
vector<int> GT[MAX_N];

stack<int> S;
bool viz[MAX_N];

int nr_ctc;
vector<int> ctc[MAX_N];

void read() {
    freopen("ctc.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        x--; y--;

        G[x].push_back(y);
        GT[y].push_back(x);
    }
    fclose(stdin);
}

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

void DFS(int v) {
    viz[v] = true;
    for(int i = 0; i < G[v].size(); i++) {
        int child = G[v][i];
        if(!viz[child]) {
            DFS(child);
        }
    }
    S.push(v);
}

void connect(int v, int comp) {
    viz[v] = true;
    ctc[comp].push_back(v);

    for(int i = 0; i < GT[v].size(); i++) {
        int child = GT[v][i];
        if(!viz[child]) {
            connect(child, comp);
        }
    }
}

void solve() {
    for(int i = 0; i < n; i++) {
        if(!viz[i]) {
            DFS(i);
        }
    }

    memset(viz, false, n);

    while(!S.empty()) {
        int v = S.top();
        S.pop();

        if(!viz[v]) {
            connect(v, nr_ctc++);
        }
    }
}

int main() {
    read();
    solve();
    write();
    return 0;
}