Cod sursa(job #3347251)

Utilizator And_etcAndrei P And_etc Data 15 martie 2026 21:10:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> v[100555];

int p[100555],l[100555],d[100555];

stack <int> st;

int ct;

vector <int> ctc[100555];

void dfs(int k,int i)
{
    st.push(k);
    l[k]=i;
    d[k]=i;
    for(auto a:v[k])
    {
        if(p[a]!=k)
        {
            if(p[a]==0)
            {
                p[a]=k;
                dfs(a,i+1);
                l[k]=min(l[k],l[a]);
                if(l[a]>=d[k])
                {
                    ++ct;
                    int vl;
                    ctc[ct].push_back(k);
                    do
                    {
                        vl=st.top();
                        st.pop();
                        ctc[ct].push_back(vl);
                    }
                    while(vl!=a);
                }
            }
            else if(d[a]<d[k])
            {
                l[k]=min(l[k],d[a]);
            }
        }
    }
}

int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int n,m,x,y;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;++i)
    {
        if(p[i]==0)
        {
            p[i]=-1;
            dfs(i,1);
        }
    }
    cout<<ct<<"\n";
    for(int i=1;i<=ct;++i)
    {
        sort(ctc[i].begin(),ctc[i].end());
        for(auto a:ctc[i])
        {
            cout<<a<<" ";
        }
        cout<<"\n";
    }
    return 0;
}