Cod sursa(job #3374362)

Utilizator ericneaguEric Neagu ericneagu Data 8 noiembrie 2026 23:23:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n, m;
vector<int> graf[100005];     
int tin[100005];             
int low[100005];              
int par[100005];              
int poz[100005];              
int t;                     

vector<int> st;               
vector<int> cs;       
vector<vector<int>> comps; 

int main() {
    f>>n>>m;

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

    for (int s=1; s<= n;s++) {
        if (tin[s] != 0) continue;
        t++;
        tin[s] = t;
        low[s] = t;
        par[s] = 0;
        st.push_back(s);
        cs.push_back(s);

        while (!cs.empty()) {
            int v = cs.back();              
            if (poz[v] < (int)graf[v].size()) {
                int u = graf[v][poz[v]];
                poz[v]++;
                if (u == par[v]) continue;
                if (tin[u] != 0) {
                    if (tin[u] < low[v]) 
                        low[v] = tin[u];
                    
                } else {
                    par[u] = v;
                    t++;
                    tin[u] = t;low[u] = t;
                    st.push_back(u);
                    cs.push_back(u);
                }
            } else {
                cs.pop_back();
                int p = par[v];
                if (p != 0) {
                    if (low[v] < low[p]) 
                        low[p] = low[v];
            
                    if (low[v] >= tin[p]) {
                        vector<int> comp;
                        while (true) {
                            int x = st.back();
                            st.pop_back();
                            comp.push_back(x);
                            if (x == v) break;   
                        }
                        comp.push_back(p); 
                        comps.push_back(comp);
                    }
                }
            }
        }
    }
    g<<comps.size()<< '\n';
    for (auto c : comps) {
        for (int x : c) 
            g<< x<< " ";
        g << '\n';
    }
    return 0;
}