Cod sursa(job #1393998)

Utilizator retrogradLucian Bicsi retrograd Data 19 martie 2015 21:58:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<vector>
#include<stack>

using namespace std;
typedef int var;

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

#define MAXN 100005

var n, m;
vector<var> G[MAXN];

var D[MAXN], LOW[MAXN];
bool IN[MAXN];

var nr_ctc = 0;
stack<var> ST;
vector<var> CTC[MAXN];

var t = 0;

void dfs(var node) {

    LOW[node] = D[node] = ++t;
    ST.push(node);
    IN[node] = 1;

    for(auto vec : G[node]) {
        if(!D[vec]) {
            dfs(vec);
        }
        if(IN[vec])
            LOW[node] = min(LOW[node], LOW[vec]);
    }

    if(LOW[node] == D[node]) {
        nr_ctc ++;
        var top = 0;
        while(top != node) {
            top = ST.top();
            ST.pop();
            IN[top] = 0;
            CTC[nr_ctc].push_back(top);
        }
    }
}

int main() {

    var a, b;

    var n, m;
    fin>>n>>m;
    while(m--) {
        fin>>a>>b;
        G[a].push_back(b);
    }

    for(var i=1; i<=n; i++) {
        if(!D[i])
            dfs(i);
    }

    fout<<nr_ctc<<'\n';
    for(var i=1; i<=nr_ctc; i++) {
        for(auto node : CTC[i]) {
            fout<<node<<" ";
        }
        fout<<'\n';
    }

    return 0;
}