Cod sursa(job #1320223)

Utilizator retrogradLucian Bicsi retrograd Data 17 ianuarie 2015 18:44:53
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 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], VIZ[MAXN];

void dfi(var node) {
    VIZ1[node] = true;
    for(vector<var>::iterator it = G[node].begin(); it!=G[node].end(); ++it) {
        if(!VIZ1[*it] && !VIZ[*it]) {
            dfi(*it);
        }
    }
}

void dfe(var node) {
    VIZ2[node] = true;
    if(VIZ1[node] = 1) {
        VIZ[node] = 1;
        CC[cur_cc].push_back(node);
    }
    for(vector<var>::iterator it = Gt[node].begin(); it!=Gt[node].end(); ++it) {
        if(!VIZ2[*it] && !VIZ[*it]) {
            dfe(*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(!VIZ[i]) {
            cur_cc++;
            for(var j=1; j<=n; j++) {
                VIZ1[j] = VIZ2[j] = 0;
            }
            dfi(i);
            dfe(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;
}