Cod sursa(job #1955225)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 5 aprilie 2017 21:13:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");

const int NMax = 1e5 + 50;
const int inf = 2e9 + 5;

int N,M,nrComp;
int depth[NMax],lowPoint[NMax];
// depth[i] = adancimea nodului i in dfs
// lowPoint[i] = adancimea cea mai mica la care se poate ajunge
//               dintr-un vecin al oricarui nod din subarborele lui i

vector<int> v[NMax];
vector<int> comp[NMax];
// v - liste de adiacenta
// comp[i] - nodurile din componenta biconexa cu numarul de ordine i

struct muchie {
    int x,y;
    muchie(int _x = 0,int _y = 0) {
        x = _x;
        y = _y;
    }
    bool equals(muchie b) {
        return (x == b.x) && (y == b.y);
    }
};
stack<muchie> st;
// st - stiva folosita pentu determinarea componentelor biconexe

void dfs(int,int);
void getComp(muchie);

int main() {

    in>>N>>M;
    for (int i=1;i<=M;++i) {
        int x,y;
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1,0);

    out<<nrComp<<'\n';
    for (int i=1;i<=nrComp;++i) {
        while (comp[i].size()) {
            out<<comp[i].back()<<' ';
            comp[i].pop_back();
        }

        out<<'\n';
    }

    in.close();out.close();
    return 0;
}

void dfs(int nod,int dad) {
    st.push(muchie(dad,nod));
    depth[nod] = depth[dad] + 1;

    lowPoint[nod] = depth[dad];
    for (int k=0;k < (int)v[nod].size();++k) {
        int next = v[nod][k];

        if (next == dad) {
            continue;
        }
        if (depth[next]) {
            lowPoint[nod] = min(lowPoint[nod],depth[next]);
            continue;
        }
        dfs(next,nod);

        lowPoint[nod] = min(lowPoint[nod],lowPoint[next]);
        // nod este punct de articulatie doar daca descendentii sai nu pot ajunge
        // mai in sus pe graf decat prin el
        // fiecare punct de articulatie determina o componenta biconexa
        // in subarborele sau
        if (lowPoint[next] == depth[nod]) {
            getComp(muchie(nod,next));
        }
    }
}

void getComp(muchie m) {
    ++nrComp;

    while (true) {
        muchie aux = st.top();
        comp[nrComp].push_back(aux.y);
        if ( !aux.equals(m) ) {
            st.pop();
        }
        else {
            break;
        }
    }

    comp[nrComp].push_back(st.top().x);
    st.pop();
}