Cod sursa(job #3355648)

Utilizator Benjamin4321234Benjamin Secara Benjamin4321234 Data 24 mai 2026 14:47:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;

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

int n,m,cnt,now,x,y;
vector<int> v[100001];
vector<vector<int>> ans;

int seen[100001],lowest[100001],st[100001];

void dfs(int x, int t)
{
    lowest[x]=seen[x]=cnt;
    cnt++;
    now++;
    st[now]=x;
    for(auto u:v[x])
    {
        if(!seen[u]) ///e prima data cand ajungem
        {
            int p=now;
            dfs(u,x);
            if(lowest[u]>=seen[x]){///nu este alt nod mai sus decat x, este p de articulatie
                vector<int> rez;
                rez.push_back(x);
                while(p<now){
                    rez.push_back(st[now]);
                    now--;
                }
                ans.push_back(rez);
            }
            lowest[x]=min(lowest[x],lowest[u]);
            ///propagam in sus cel mai mic
        }
        else if(u!=t)///ne reintoarcem printr-o muchie punctata
        {
            lowest[x]=min(lowest[x],seen[u]);
        }
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    fout<<ans.size()<<'\n';
    for(auto u:ans){
        for(auto u1:u){
            fout<<u1<<" ";
        }
        fout<<'\n';
    }
    return 0;
}