Cod sursa(job #3294336)

Utilizator Andrei012Trache Andrei Andrei012 Data 21 aprilie 2025 18:31:05
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;
#define mp make_pair

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

int parc[100001],lvl[100001],ans;

vector<pair<int,int> > cb[100001];
stack<pair<int,int> > st;
vector<int> v[100001];
set<int> ans1;


int dfs(int node) {
    parc[node] = 1;
    int l = (1<<30);
    for (int i : v[node]) {
        st.push(mp(node, i));
        if (parc[i] == 1) {
            if (lvl[node]<=lvl[i])
                st.pop();
            l=min(l,lvl[i]);
            continue;
        }
        else {
            lvl[i]=lvl[node]+1;
            int newL = dfs(i);
            l = min(l,newL);
            if (newL >= lvl[node]) {
                ++ans;
                while(st.size() && st.top() != mp(node,i)) {
                    cb[ans].push_back(st.top());
                    st.pop();
                }
                cb[ans].push_back(st.top());
                st.pop();
            }
        }
    }
    return l;
}


int main() {
    int i,j,k,n,m,x,y;
    in>>n>>m;
    for(i=0;i<m;i++) {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    out<<ans<<'\n';
    for (i=1;i<=ans;i++) {
        ans1.clear();
        for (auto j : cb[i]) {
            ans1.insert(j.first);
            ans1.insert(j.second);
        }
        for (auto j : ans1) {
            out<<j<<' ';
        }
        out<<'\n';
    }
    return 0;
}