Cod sursa(job #2343253)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 13 februarie 2019 20:36:32
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
#define LMAX 100001
int n,m;
vector<int> G[LMAX];
int time_disc=0,low[LMAX],disc[LMAX];
stack<pair<int,int> > st;
int nr_comp=0;
vector<int> C[LMAX];
void make_component(pair<int,int> edge){
    ++nr_comp;
    pair<int,int> it;
    do{
        it=st.top();
        st.pop();
        C[nr_comp].push_back(it.first);
        C[nr_comp].push_back(it.second);
    }while(it!=edge);
    sort(C[nr_comp].begin(),C[nr_comp].end());
    C[nr_comp].resize(distance(C[nr_comp].begin(),unique(C[nr_comp].begin(),C[nr_comp].end())));
}
void dfs(int node,int parent){
    disc[node]=low[node]=(++time_disc);
    for(auto it : G[node]){
        if(it==parent) continue;
        else if(!disc[it]){
            st.push({node,it});
            dfs(it,node);
            low[node]=min(low[node],low[it]);
            if(low[it]>=disc[node])
                make_component({node,it});
        }
        else low[node]=min(low[node],disc[it]);
    }
}
int main(){
 //   freopen(".in","r",stdin);
 //   freopen(".out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d %d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,-1);
    printf("%d\n",nr_comp);
    for(int i=1;i<=nr_comp;++i){
        for(auto it : C[i])
            printf("%d ",it);
        printf("\n");
    }
    return 0;
}