Cod sursa(job #2871027)

Utilizator cezar.balutaCezar Baluta cezar.baluta Data 12 martie 2022 20:06:24
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
/*
                         __
                   _.--""  |
    .----.     _.-'   |/\| |.--.
    |    |__.-'   _________|  |_)  _______________
    |  .-""-.""""" ___,    `----'"))   __   .-""-.""""--._
    '-' ,--. `    |Cezar| .---.       |:.| ' ,--. `      _`.
     ( (    ) ) __|  7  |__\\|// _..-- \/ ( (    ) )--._".-.
      . `--' ;\__________________..--------. `--' ;--------'
       `-..-'                               `-..-'
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int N = 1e5 + 5;
vector <int> v[N];
int t[N],t_min[N];
int timp = 1,nr_componente;
stack<int>s;
vector<int>rez[N];

ofstream out("biconex.out");

void dfs(int x, int tata){
   // cout<<x<<' ';
   s.push(x);
    t[x] = t_min[x] = timp++;
    for(auto y:v[x]){
        if(t[y] == 0){
            dfs(y,x);
            t_min[x] = min(t_min[x],t_min[y]);
            if(t_min[y]>=t[x]){
                while(s.top()!=y){
                    rez[nr_componente].push_back(s.top());
                    s.pop();
                }
                s.pop();
                rez[nr_componente].push_back(y);
                rez[nr_componente].push_back(x);
                nr_componente++;
            }
        }
        else if(y!=tata){
            t_min[x] = min(t_min[x],t[y]);
        }

    }
}

int main() {
    ifstream in("biconex.in");

    int n,m,x,y;
    in>>n>>m;
    while(m--){
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(t[i] == 0)
            dfs(i,0);
    }
    out<<nr_componente<<'\n';
    for(int i=0;i<nr_componente;i++){
        for(auto y:rez[i])
            out<<y<<' ';
        out<<'\n';
    }
    return 0;
}