Cod sursa(job #1320290)

Utilizator retrogradLucian Bicsi retrograd Data 17 ianuarie 2015 20:03:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<vector>
#include<cstring>
#define MAXN 100001

using namespace std;

typedef int var;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector<var> G[MAXN];
vector<var> Gt[MAXN];
vector<var> CC[MAXN];
var n;
var cur_cc;
bool VIZ1[MAXN], VIZ2[MAXN];
vector<int> ST;

void dfs1(var node) {
    VIZ1[node] = 1;
    for(vector<var>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
        if(!VIZ1[*it])
            dfs1(*it);
    }
    ST.push_back(node);
}

void dfs2(var node) {
    VIZ2[node] = 1;
    CC[cur_cc].push_back(node);
    for(vector<var>::iterator it = Gt[node].begin(); it != Gt[node].end(); ++it) {
        if(!VIZ2[*it])
            dfs2(*it);
    }
}

int main() {
    var m, a, b;

    fin>>n>>m;
    while(m--) {
        fin>>a>>b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }
    for(var i=1; i<=n; i++) {
        if(!VIZ1[i])
            dfs1(i);
    }
    for(var i=n-1; i>=0; i--) {
        if(!VIZ2[ST[i]]) {
            cur_cc++;
            dfs2(ST[i]);
        }
    }

    fout<<cur_cc<<'\n';
    for(var i=1; i<=cur_cc; ++i) {
        for(vector<var>::iterator it = CC[i].begin(); it!=CC[i].end(); ++it)
            fout<<*it<<" ";
        fout<<'\n';
    }
    return 0;
}