Cod sursa(job #2824998)

Utilizator Ioana_GaborGabor Ioana Ioana_Gabor Data 3 ianuarie 2022 20:15:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb

#include <bits/stdc++.h>
#define NMAX 100000

using namespace std;

ifstream fi("biconex.in");
ofstream fo("biconex.out");

int n,m,x,y,cnt,top;
vector<int> G[NMAX+5];
int ind[NMAX+5], low[NMAX+5];
pair<int,int> st[2*NMAX+5];
vector<vector<int>>comp;
vector<int> aux;

void read(){
    fi>>n>>m;
    for(int i=1;i<=m;i++){
        fi>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void elimin(int a,int b){
    do{
        x=st[top].first,y=st[top].second;
        aux.push_back(y);
        top--;
    }while(a!=x&&b!=y);
    aux.push_back(x);
    comp.push_back(aux);
    aux.clear();
}

void dfs(int nod,int par){
    ind[nod]=low[nod]=++cnt;
    for(int i=0;i<G[nod].size();i++){
        int chd=G[nod][i];
        if(chd!=par){
            if(!ind[chd]){
                st[++top]=make_pair(nod,chd);
                dfs(chd,nod);
                low[nod]=min(low[nod],low[chd]);
                if(low[chd]>=ind[nod]){
                    elimin(nod,chd);
                }
            }else{
                low[nod]=min(low[nod],ind[chd]);
            }
        }
    }
}

void write(){
    fo<<comp.size()<<'\n';
    for(int i=0;i<comp.size();i++){
        for(int j=0;j<comp[i].size();j++){
            fo<<comp[i][j]<<' ';
        }
        fo<<'\n';
    }
}

int main(){
    read();
    dfs(1,0);
    write();
    fi.close();
    fo.close();    
}