Cod sursa(job #3224503)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 15 aprilie 2024 15:43:57
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAX = 1e5 + 1;

vector<int> comp[MAX];
vector<int> adj[MAX];
int level[MAX];
bool viz[MAX];
int low[MAX];
int noComp;
int n, m;

stack<int> S;
void dfs(int node = 1, int dad = 0) {
    level[node] = level[dad] + 1;
    low[node] = level[dad] + 1; 
    viz[node] = 1;

    S.push(node);
    for(int nxt : adj[node]) 
        if(nxt != dad) {
            if(viz[nxt])
                low[node] = min(low[node], level[nxt]);
            else {
                dfs(nxt, node);

                low[node] = min(low[node], low[nxt]);
                if(low[nxt] >= level[node]) {
                    ++noComp;
                    while(S.top() != nxt) {
                        comp[noComp].emplace_back(S.top());
                        S.pop();
                    }

                    comp[noComp].emplace_back(nxt);
                    S.pop();
                    comp[noComp].emplace_back(node);
                }
            }
        }
}

signed main() 
{  
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    int x, y;
    for(int i = 0; i < m; i++) {
        cin >> x >> y;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }

    dfs();

    cout << noComp << '\n';
    for(int i = 1; i <= noComp; i++) {
        for(const int& x : comp[i])
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}