Cod sursa(job #1983042)

Utilizator MaligMamaliga cu smantana Malig Data 21 mai 2017 08:57:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <stack>

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

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

int N,M,nrComp;
int depth[NMax],lowPoint[NMax];
vector<int> comp[NMax];
vector<int> v[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;
    while (M--) {
        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 (auto j : comp[i]) {
            out<<j<<' ';
        }
        out<<'\n';
    }

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

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

    for (auto nxt : v[node]) {
        if (depth[nxt]) {
            lowPoint[node] = min(lowPoint[node],depth[nxt]);
            continue;
        }

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

void getComp(muchie m) {
    muchie aux;
    while (!((aux = st.top()) == m)) {
        comp[nrComp].push_back(aux.y);
        st.pop();
    }
    comp[nrComp].push_back(aux.y);
    comp[nrComp].push_back(aux.x);
    st.pop();
}