Cod sursa(job #1165419)

Utilizator SRaduRadu Szasz SRadu Data 2 aprilie 2014 17:55:57
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAX = 101101;

#define x first
#define y second

int N, M;
int Level[MAX], Highest[MAX];

bool viz[MAX];

vector<int> V, G[MAX];
vector< pair<int, int> > Edges;
vector< vector<int> > BC;

void citire() {
    ifstream in("biconex.in");
    in >> N >> M;
    for(int i = 1, A, B; i <= M; i++) {
        in >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    } in.close();
}

void dfs(int nod, int Dad, int Nivel) {
    //cerr << "Entered dfs for node " << nod << "\n";
    viz[nod] = true;
    Level[nod] = Highest[nod] = Nivel;
    for(size_t i = 0; i < G[nod].size(); i++) {
        int dest = G[nod][i];
        //cerr << "Dest is " << dest << "\n";
        if(dest == Dad) continue;
        if(!viz[dest]) {
            //cerr << "Added " << nod << " " << dest << " to edges\n";
            Edges.push_back(make_pair(nod, dest));
            dfs(dest, nod, Nivel + 1);
            Highest[nod] = min(Highest[nod], Highest[dest]);
        } else {
            Highest[nod] = min(Highest[nod], Level[dest]);
            continue;
        }
        if(Highest[dest] >= Level[nod]) {
            //cerr << "We are in node " << nod << " and we are trying to delete\n";
            V.clear();
            int A, B;
            do {
                A = Edges.back().x, B = Edges.back().y;
                //cerr << "Popped " << A << " " << B << " from edges\n";
                Edges.pop_back();
                V.push_back(A);
                V.push_back(B);
            } while(!V.empty() && nod != A && dest != B);
            sort(V.begin(), V.end());
            V.erase(unique(V.begin(), V.end()), V.end());
            BC.push_back(V);
        }
    }
    //cerr << "Exiting dfs for node " << nod << "\n";
}

void solve() {
    for(int i = 1; i <= N; i++) {
        if(!viz[i])
            dfs(i, 0, 1);
    }
}

void afisare() {
    ofstream out("biconex.out");
    out << BC.size() << "\n";
    for(size_t i = 0; i < BC.size(); i++) {
        for(size_t j = 0; j < BC[i].size(); j++)
            out << BC[i][j] << " ";
        out << "\n";
    }
}

int main() {
    citire();
    solve();
    afisare();

}