Cod sursa(job #2981190)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 17 februarie 2023 14:55:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

const int NMAX = 1e5;

vector <int> g[NMAX + 1];
vector <vector <int>> cbc;
int tmin[NMAX + 1], in[NMAX + 1], timp;
stack <int> stiva;

void adauga_cbc(int x, int y, vector <int> &v){

    while(stiva.top() != y){

        v.push_back(stiva.top());
        stiva.pop();

    }

    v.push_back(x);
    v.push_back(y);
    stiva.pop();


}

void dfs(int x, int t){

    tmin[x] = in[x] = ++timp;
    stiva.push(x);

    for(auto y : g[x]){

        if(y == t)
            continue;

        if(!in[y]){

            dfs(y, x);
            tmin[x] = min(tmin[x], tmin[y]);

            if(tmin[y] >= in[x]){

                //art[x] = 1;
                vector <int> c;
                adauga_cbc(x, y, c);
                cbc.push_back(c);

            }

        }else
            tmin[x] = min(tmin[x], in[y]);

    }


}

int main(){

    int n = 0, m = 0;
    cin >> n >> m;

    for(int i = 0; i < m; i++){

        int x = 0, y = 0;
        cin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);

    }

    for(int i = 1; i <= n; i++)
        if(!in[i])
            dfs(i, 0);

    cout << cbc.size() << "\n";
    for(auto y : cbc){
        for(auto e : y){

            cout << e << " ";

        }
        cout << "\n";
    }

}