Cod sursa(job #3373419)

Utilizator lea_Lea Ales lea_ Data 6 noiembrie 2026 22:40:43
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> adj[100005];
int tin[100005], low[100005], parent[100005], it[100005];
int timer_=0;
vector<vector<int>>comps;

void dfs(int s){
    vector<int> st, stk;
    st.push_back(s);
    stk.push_back(s);

    tin[s] =low[s]=++timer_;
    parent[s]=0;

    while(!st.empty()) {
        int v=st.back();
        if(it[v]<(int)adj[v].size()){
            int u=adj[v][it[v]++];
            if(u==parent[v]) continue;
            if(tin[u]){
                low[v]=min(low[v], tin[u]);
            } else{
                parent[u]=v;
                tin[u]=low[u]=++timer_;
                st.push_back(u);
                stk.push_back(u);
            }
        } else{
            st.pop_back();
            int p=parent[v];
            if(p){
                low[p]=min(low[p],low[v]);
                if(low[v]>=tin[p]){
                    vector<int> comp;
                    int w;
                    do{
                        w=stk.back();
                        stk.pop_back();
                        comp.push_back(w);
                    } while(w!=v);
                    comp.push_back(p);
                    comps.push_back(comp);
                }
            }
        }
    }
}

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(!tin[i])
            dfs(i);

    fout<<comps.size()<<"\n";
    for(size_t i=0; i<comps.size(); i++){
        for(size_t j=0; j<comps[i].size();j++)
            fout<<comps[i][j]<<(j+1<comps[i].size() ? " " : "\n");
    }
    return 0;
}