Cod sursa(job #2373899)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 7 martie 2019 15:44:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;
#define LMAX 100005
vector<int> G[LMAX];
int low[LMAX],disc[LMAX],time_disc=0;
stack<pair<int,int> > st;
int nr_comp=0;
vector<int> bi[LMAX];
void make_comp(pair<int,int> muc){
    ++nr_comp;
    pair<int,int> top;
    do{
       top=st.top();
       st.pop();
       bi[nr_comp].push_back(top.first);
       bi[nr_comp].push_back(top.second);
    }while(muc!=top);
    sort(bi[nr_comp].begin(),bi[nr_comp].end());
    bi[nr_comp].resize(distance(bi[nr_comp].begin(),unique(bi[nr_comp].begin(),bi[nr_comp].end())));
}
void dfs(int nod,int tata){
    low[nod]=disc[nod]=(++time_disc);
    for(auto it : G[nod]){
        if(it==tata)
            continue;
        if(!disc[it]){
            st.push({nod,it});
            dfs(it,nod);
            low[nod]=min(low[nod],low[it]);
            if(disc[nod]<=low[it])
                make_comp({nod,it});
        }
        else low[nod]=min(low[nod],disc[it]);
    }
}
int main(){
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        int from,to;
        scanf("%d %d",&from,&to);
        G[from].push_back(to);
        G[to].push_back(from);
    }
    dfs(1,-1);
    printf("%d\n",nr_comp);
    for(int i=1;i<=nr_comp;++i){
        for(auto it : bi[i])
            printf("%d ",it);
        printf("\n");
    }
    return 0;
}