Cod sursa(job #1329213)

Utilizator retrogradLucian Bicsi retrograd Data 29 ianuarie 2015 11:05:42
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include<fstream>
#include<vector>
#include<stack>
#include<utility>

#define MAXN 100001

using namespace std;
typedef int var;

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

stack<pair<var, var> >ST;
vector<var> G[MAXN];
var PARENT[MAXN], D[MAXN], LOW[MAXN];
vector<var> CBC[MAXN];
bool VIZ[MAXN];
var n;

var time, cbc;
void dfs(var node) {
    VIZ[node] = 1;
    D[node] = ++time;
    LOW[node] = D[node];

    for(vector<var>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
        const var &vec = *it;
        if(vec == PARENT[node]) continue;

        if(!VIZ[vec]) {
            VIZ[vec] = 1;
            PARENT[vec] = node;
            ST.push(make_pair(node, vec));
            dfs(vec);

            LOW[node] = min(LOW[node], LOW[vec]);

            if(LOW[vec] >= D[node]) {
                cbc++;
                CBC[cbc].push_back(ST.top().second);
                while(ST.top() != make_pair(PARENT[node], node)) {
                    CBC[cbc].push_back(ST.top().first);
                    ST.pop();
                }

            }
        } else if(LOW[vec] < LOW[node]) {
            LOW[node] = LOW[vec];
        }
    }
}

int main() {
    var m, a, b;
    fin>>n>>m;
    for(var i=1; i<=m; i++) {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ST.push(make_pair(0, 1));
    for(var i=1; i<=n; i++) {
        if(!VIZ[i]) {
            dfs(i);
        }
    }

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