Cod sursa(job #3041232)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 31 martie 2023 10:38:58
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int MAX = 1e5 + 1;

int tin[MAX] , low[MAX] , time , n , m , x , y;

bool viz[MAX];

stack <int> s;

vector <vector<int>> cb;
vector <int> aux;
vector <int> g[MAX];

void findcb( int x , int p ){

    viz[x] = 1;
    tin[x] = ++time;
    low[x] = tin[x];

    s.push(x);

    for(auto it : g[x]){

        if(it == p) continue;

        if(viz[it] == 1){

            low[x] = min(low[x],tin[it]);

            continue;
        }

        findcb(it,x);

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

        if(low[it] >= tin[x]){

            aux.clear();

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

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

            aux.push_back(s.top());

            cb.push_back(aux);
        }
    }
}

int main()
{

    cin >> n >> m;

    while(m--){

        cin >> x >> y;

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

    findcb(1,0);

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

    for(auto i : cb){

        for(auto it : i){

            cout << it << ' ';
        }

        cout << '\n';
    }

    return 0;
}