Cod sursa(job #2815943)

Utilizator VipioanaMirea Oana Teodora Vipioana Data 10 decembrie 2021 17:35:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int N=1e5+1;
int n,m,t[N],t_min[N],nrc,timp;
vector <int> a[N],cbc[N];
stack <int> stiva;

void adaugare_cbc(int x, int j){
    ++nrc;
    while(stiva.top()!=j){
        cbc[nrc].push_back(stiva.top());
        stiva.pop();
    }
    cbc[nrc].push_back(j);
    cbc[nrc].push_back(x);
    stiva.pop();
}

void dfs(int x, int tata){
    t[x]=t_min[x]=++timp;
    stiva.push(x);
    for(int j:a[x]){
        if(!t[j]){
            dfs(j,x);
            t_min[x]=min(t_min[x],t_min[j]);
            if(t_min[j]>=t[x]){
                adaugare_cbc(x,j);
            }
        }else
        if(j!=tata){
           t_min[x]=min(t_min[x],t[j]);
        }
    }
}

int main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(int i=1; i<=n; i++){
        if(!t[i])
            dfs(i,0);
    }
    cout<<nrc<<'\n';
    for(int i=1; i<=nrc; i++){
        for(int j:cbc[i])
            cout<<j<<" ";
        cout<<'\n';
    }
    return 0;
}