Cod sursa(job #2982641)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 20 februarie 2023 17:23:21
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;

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

const int MAX = 1e5 + 2;

int t[MAX] , tmin[MAX];

//t[i] = cand se ajunge de la radacina la i (ca timp);

int cerinta , n , m , x , y , timp;

bitset<MAX>b;

vector <int> pa;

vector<vector<int>>cb;

vector <int> g[MAX];

stack <int> s;


void dfs1( int x , int p){

    s.push(x);

    b[x] = 1;

    t[x] = tmin[x] = ++timp;

    for(auto it : g[x]){

        if( it == p ){

            continue;

        }else if(b[it]){

            tmin[x] = min(tmin[x],t[it]);

        }else{

            dfs1(it,x);

            tmin[x] = min(tmin[x],tmin[it]);

            if(t[x] <= tmin[it]){

                vector <int> aux;

                while(!s.empty() && s.top()!=it){

                    aux.push_back(s.top());;

                    s.pop();
                }

                aux.push_back(s.top());
                s.pop();

                aux.push_back(x);

                cb.push_back(aux);
            }
        }
    }
}

int main()
{

    cin >> n >> m;

    while(m--){

        cin >> x >> y;

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

    dfs1(1,0);

    cout << cb.size() << '\n';

    for(auto it : cb){

        for(auto y: it){

            cout << y << ' ';
        }

        cout << '\n';
    }

    return 0;
}