Cod sursa(job #3374527)

Utilizator lea_Lea Ales lea_ Data 9 noiembrie 2026 01:46:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> adj[100005];
int vizitat[100005], low[100005];
int cnt=0;
vector<vector<int>>comps;
vector<int> stiva;

void dfs(int v, int p){
    vizitat[v]=low[v]=++cnt;
    stiva.push_back(v);

    for(int u:adj[v]){
        if(u==p) continue;
        if(vizitat[u]) {
            low[v]=min(low[v],vizitat[u]);
        } else{
            dfs(u,v);
            low[v]=min(low[v],low[u]);
            if(low[u] >=vizitat[v]){
                vector<int> c;
                int w;
                do{
                    w=stiva.back();
                    stiva.pop_back();
                    c.push_back(w);
                } while(w!=u);
                c.push_back(v);
                comps.push_back(c);
            }
        }
    }
}

int main(){
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    int n,m;
    fin>>n>>m;

    for(int i=0; i<m; i++){
        int x,y;
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

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

    fout<<comps.size()<<"\n";

    for(auto c:comps){
        for(int x:c)
            fout<<x<<" ";
        fout<<"\n";
    }
    return 0;
}