Cod sursa(job #1964855)

Utilizator MaligMamaliga cu smantana Malig Data 13 aprilie 2017 19:00:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

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

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

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

struct muchie {
    int x,y;
    muchie(int _x = 0,int _y = 0) {
        x = _x; y = _y;
    }
};
stack<muchie> st;

bool operator ==(muchie a, muchie b) {
    return a.x == b.x && a.y == b.y;
}

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) {
    depth[nod] = depth[dad] + 1;
    verif[nod] = true;
    st.push(muchie(dad,nod));

    lowPoint[nod] = depth[dad];
    for (int k=0;k < (int)v[nod].size();++k) {
        int next = v[nod][k];
        if (verif[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 m) {
    ++nrComp;

    while (true) {
        muchie top = st.top();
        comp[nrComp].pb(top.y);

        if (top == m) {
            break;
        }

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