Cod sursa(job #2097854)

Utilizator MaligMamaliga cu smantana Malig Data 1 ianuarie 2018 19:04:36
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

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

#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define pb push_back
#define mp make_pair
const int NMax = 1e5 + 5;
const ll inf = 1e18 + 5;
const ll valMax = 1e6 + 5;
using zint = short;

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

void dfs(int,int);
void getComp(pair<int,int>);

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

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

void dfs(int node,int dad) {
    st.push( {dad,node} );

    lowPoint[node] = depth[node] = depth[dad] + 1;
    for (int nxt : v[node]) {
        if (lowPoint[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( {node,nxt} );
        }
    }
}

void getComp(pair<int,int> bot) {
    while (st.top() != bot) {
        comp[nrComp].pb( st.top().second );
        st.pop();
    }

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