Cod sursa(job #3226696)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 22 aprilie 2024 16:44:52
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int INF = 1e9 + 69;
const int MOD = 666013;
const int MAX = 1e5 + 2;

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 nod = 1, int dad = 0) {
    level[nod] = level[dad] + 1;
    low[nod] = level[dad] + 1;
    viz[nod] = true;            
    S.push(nod);

    for(const int &nxt : adj[nod])
        if(nxt != dad) 
            if(viz[nxt])
                low[nod] = min(low[nod], level[nxt]);
            else {
                dfs(nxt, nod);
                low[nod] = min(low[nod], low[nxt]);
                if(low[nxt] >= level[nod]) {
                    ++noComp;
                    while(S.top() != nxt) {
                        comp[noComp].emplace_back(S.top());
                        S.pop();
                    }
                    comp[noComp].emplace_back(nxt);
                    comp[noComp].emplace_back(nod);
                    S.pop();              
                }
            }

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);


    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;
}