Cod sursa(job #3346963)

Utilizator tudorhTudor Horobeanu tudorh Data 15 martie 2026 14:05:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>

using namespace std;

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


const int nmax = 1e5;

vector<int>v[nmax + 1];

int d[nmax + 1], low[nmax + 1], timer,bccs;
stack<pii>s;

vector<pii>b[nmax+1];


void get_bcc(pii e){
    bccs++;
    while(s.top()!=e){
        b[bccs].pb(s.top());
        s.pop();
    }
    b[bccs].pb(e);
    s.pop();
}

void dfs (int nod, int pr) {
    d[nod] = low[nod] = ++timer;
    int cnt = 0;
    for (int i : v[nod]) {
        if (i == pr)
            continue;
        if (d[i])
            low[nod] = min (low[nod], d[i]);
        else {
            cnt++;
            s.push({nod,i});
            dfs (i, nod);
            low[nod] = min (low[nod], low[i]);
            if(low[i]>=d[nod] || (nod==1 && cnt>=2))
                get_bcc({nod,i});
        }
    }
}
vector<int>now;

int main() {
    int n,m;
    fin>>n>>m;
    while(m--){
        int st,dr;
        fin>>st>>dr;
        v[st].pb(dr);
        v[dr].pb(st);
    }
    dfs(1,1);
    fout<<bccs<<'\n';
    for(int i=1;i<=bccs;i++){
        now.clear();
        for(pii j:b[i])
            now.pb(j.first),now.pb(j.second);
        sort(now.begin(),now.end());
        now.erase(unique(now.begin(),now.end()),now.end());
        for(int j:now)
            fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}