Cod sursa(job #2814783)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 8 decembrie 2021 16:40:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

const int N = 100005;
stack<int>s;
int n,m,t_min[N],t[N],n_cbc,timp;
vector <int> a[N],cbc[N];

void adauga_cbc(int x, int y){
    n_cbc++;
    while (s.top() != y){
        cbc[n_cbc].push_back(s.top());
        s.pop();
    }
    cbc[n_cbc].push_back(y);
    cbc[n_cbc].push_back(x);
    s.pop();
}

void dfs(int x, int tata){
    timp++;
    t_min[x] = t[x] = timp;
    s.push(x);
    for(auto y: a[x]){
        if(t[y] == 0){
            dfs(y,x);
            t_min[x] = min(t_min[x],t_min[y]);
            if(t_min[y] >=t[x])
                adauga_cbc(x,y);
        }
        else if(y!=tata){
            t_min[x] = min(t_min[x],t[y]);
        }
    }
}

int main() {
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    in>>n>>m;
    for (int i = 0; i < m; i++){
        int x,y;
        in>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i=1;i<=n;i++){
        if (t[i] == 0)
            dfs(i,0);
    }
    out<<n_cbc<<'\n';
    for (int i=1;i<=n_cbc;i++){
        for (auto x: cbc[i])
            out<<x<<' ';
        out<<'\n';
    }
    return 0;
}