Cod sursa(job #1973870)

Utilizator MaligMamaliga cu smantana Malig Data 26 aprilie 2017 10:32:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

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

#define pb push_back
const int NMax = 1e5 + 5;

int N,M,nrComp;
int lowPoint[NMax],depth[NMax];
bool viz[NMax];
vector<int> v[NMax];
vector<int> comp[NMax];

struct muchie {
    int x,y;
    muchie(int _x = 0,int _y = 0) {
        x = _x;
        y = _y;
    }
};
bool operator == (muchie a,muchie b) {
    return a.x == b.x && a.y == b.y;
}

stack<muchie> st;

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].pb(y);
        v[y].pb(x);
    }

    dfs(1,0);

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

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

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

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

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

        dfs(next,nod);
        lowPoint[nod] = min(lowPoint[nod],lowPoint[next]);

        if (lowPoint[next] >= depth[nod]) {
            getComp(muchie(nod,next));
        }
    }
}

void getComp(muchie start) {
    ++nrComp;
    muchie aux;
    do {
        aux = st.top();
        comp[nrComp].pb(aux.y);
        st.pop();
    }
    while (!(aux == start));
    comp[nrComp].pb(aux.x);
}