Cod sursa(job #1956110)

Utilizator MaligMamaliga cu smantana Malig Data 6 aprilie 2017 15:02:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 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];
vector<int> v[NMax];

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;
    }
};
vector<int> comp[NMax];
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].push_back(y);
        v[y].push_back(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 node,int dad) {
    depth[node] = depth[dad] + 1;
    st.push(muchie(dad,node));

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

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

        dfs(next,node);
        lowPoint[node] = min(lowPoint[node],lowPoint[next]);
        if (lowPoint[next] == depth[node]) {
            getComp(muchie(node,next));
        }
    }
}

void getComp(muchie m) {
    ++nrComp;
    while (true) {
        muchie tp = st.top();
        comp[nrComp].push_back(tp.y);

        if (m.equals(tp)) {
            break;
        }
        st.pop();
    }

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