Cod sursa(job #3251874)

Utilizator not_anduAndu Scheusan not_andu Data 27 octombrie 2024 16:33:35
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

#define INFILE "biconex.in"
#define OUTFILE "biconex.out"

const int N_MAX = 100000;

int n, m;
int d[N_MAX + 5];
int level[N_MAX + 5];
bool visited[N_MAX + 5];
vector<int> adj[N_MAX + 5];

stack<int> s;
vector<vector<int> > ans;

void addBiconexComponent(int node, int son){

    vector<int> aux;
    while(!s.empty() && s.top() != son){
        aux.push_back(s.top());
        s.pop();
    }
    s.pop();

    aux.push_back(son);
    aux.push_back(node);

    ans.push_back(aux);

}

void dfs(int node, int parent){

    visited[node] = true;

    for(auto &to : adj[node]){
        if(to == parent) continue;
        if(visited[to]) d[node] = min(d[node], level[to]);
        else {
            s.push(to);
            level[to] = level[node] + 1;
            dfs(to, node);
            d[node] = min(d[node], d[to]);
            if(d[to] >= level[node]){
                addBiconexComponent(node, to);
            }
        }
    }

}

void solve(){

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int node1, node2; cin >> node1 >> node2;
        adj[node1].push_back(node2);
        adj[node2].push_back(node1);
    }

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

    cout << ans.size() << '\n';
    for(int i = 0; i < ans.size(); ++i){
        for(auto &node : ans[i]){
            cout << node << " ";
        }
        cout << '\n';
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    solve();
    return 0;
}