Cod sursa(job #3283815)

Utilizator tudor_costinCostin Tudor tudor_costin Data 10 martie 2025 15:55:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int Nmax=1e5+5;
vector<int> v[Nmax];
int tin[Nmax],low[Nmax];
vector<vector<int>> ans;
bitset<Nmax> viz;
int timer=1;
stack<int> st;
void dfs(int nod,int prv)
{
    st.push(nod);
    viz[nod]=1;
    tin[nod]=timer++;
    low[nod]=tin[nod];
    for(int u:v[nod])
    {
        if(u==prv) continue;
        if(!viz[u])
        {
            dfs(u,nod);
            low[nod]=min(low[nod],low[u]);
        }
        else low[nod]=min(low[nod],tin[u]);
    }
    if(prv!=0 && low[nod]>=tin[prv])
    {
        ///nod->prv e crit edge
        vector<int> c;
        while(true)
        {
            /// adaug nodurile din "subarborele" lui nod
            int x=st.top();
            st.pop();
            c.push_back(x);
            if(x==nod) break;
        }
        /// subarb lui nod + prv formeaza o componenta biconexa maxima
        c.push_back(prv);
        ans.push_back(c);
    }
}
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    fout<<ans.size()<<'\n';
    for(auto vi:ans)
    {
        for(auto x:vi) fout<<x<<' ';
        fout<<'\n';
    }
    return 0;
}