Cod sursa(job #3361100)

Utilizator mtcmtcmtc mtc mtcmtc Data 20 iulie 2026 14:42:37
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int maxn=1e5+5;
vector<int>adj[maxn];
struct s{
    int a,b;
};
stack<s>muchii;
int lvl[maxn],low[maxn];
bool vis[maxn],cp[maxn];
vector<set<int>>cmp;
void dfs(int nod,int ant,int l){
    vis[nod]=1;
    lvl[nod]=low[nod]=l;
    int cnt=0;
    for(auto e:adj[nod]){
        if(e==ant) continue;
        if(vis[e]){
            low[nod]=min(low[nod],lvl[e]);
            continue;
        }
        muchii.push({nod,e});
        dfs(e,nod,l+1);
        low[nod]=min(low[nod],low[e]);
        if(low[e]>=lvl[nod]){
            cp[nod]=1;
            set<int>elem;
            while(1){
                s x=muchii.top();
                muchii.pop();
                elem.insert(x.a);
                elem.insert(x.b);
                if(x.a==nod&&x.b==e) break;
            }
            cmp.push_back(elem);
        }
        cnt++;
    }
    if(nod==1&&cnt>1){
        cp[1]=1;
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,0,1);
    cout<<cmp.size()<<'\n';
    for(int i=0;i<cmp.size();i++){
        for(auto e:cmp[i]){
            cout<<e<<" ";
        }
        cout<<'\n';
    }
    return 0;
}