Cod sursa(job #1998164)

Utilizator MaligMamaliga cu smantana Malig Data 6 iulie 2017 19:48:22
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <stack>
#include <vector>

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

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

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

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

stack<elem> st;

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

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 (int e : comp[i]) {
            out<<e<<' ';
        }
        out<<'\n';
    }

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

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

    for (int 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]) {
            getComp(elem(node,nxt));
        }
    }
}

void getComp(elem first) {
    ++nrComp;
    while (!(st.top() == first)) {
        comp[nrComp].pb(st.top().y);
        st.pop();
    }

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