Cod sursa(job #1393989)

Utilizator retrogradLucian Bicsi retrograd Data 19 martie 2015 21:49:49
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 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];

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


void dfs(var node, var depth) {
    D[node] = depth;
    LOW[node] = D[node];
    ST.push(node);

    for(auto vec : G[node]) {
        if(!D[vec])
            dfs(vec, depth+1);
        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();
            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, 1);
    }

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

    return 0;
}