Cod sursa(job #3332230)

Utilizator WiseAndrei4Vetrila Andrei WiseAndrei4 Data 5 ianuarie 2026 14:25:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define ll long long
// #define fin cin
// #define gout cout
using namespace std;
ifstream fin("biconex.in");
ofstream gout("biconex.out");
void componente(int x,int t,vector<vector<int>>&g,int &n, vector<vector<int>>&cb,
                vector<int>&niv,vector<int>&nma,vector<bool>&viz,vector<int>&st)
{
    nma[x]=niv[x]=niv[t]+1;
    viz[x]=1;
    st.push_back(x);
    for(auto i:g[x])
    {
        if(i==t)continue;
        if(viz[i])nma[x]=min(nma[x],niv[i]);
        else
        {
            componente(i,x,g,n,cb,niv,nma,viz,st);
            nma[x]=min(nma[x],nma[i]);
            if(niv[x]<=nma[i])
            {
                cb.push_back(vector<int>(0));
                while(st.back()!=i)
                {
                    cb.back().push_back(st.back());
                    st.pop_back();
                }
                st.pop_back();
                cb.back().push_back(i);
                cb.back().push_back(x);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    gout.tie(0);
    int n,m,x,y;
    fin>>n>>m;
    vector<vector<int>>g(n+1,vector<int>(0)),cb;
    vector<int>niv(n+1,0),nma(n+1,0),st;
    vector<bool>viz(n+1,0);
    while(m--)
    {
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    componente(1,0,g,n,cb,niv,nma,viz,st);
    gout<<cb.size()<<'\n';
    for(auto i:cb)
    {
        sort(i.begin(),i.end());
        for(auto j:i)gout<<j<<' ';
        gout<<'\n';
    }
    return 0;
}