Cod sursa(job #3345343)

Utilizator tonealexandruTone Alexandru tonealexandru Data 9 martie 2026 12:11:21
Problema Componente biconexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1005;
vector<int> adj[NMAX];
int disc[NMAX], low[NMAX]; /// low - nivelul min la care se poate intoarce
stack<pair<int, int>> st;
set<int> comp[NMAX];

int bcc = 0; /// numarul de componente

void dfs(int nod, int dad)
{
    disc[nod] = disc[dad] + 1;
    low[nod] = disc[nod];

    for(auto x : adj[nod])
    {
        if(x == dad)
            continue;

        if(disc[x])
            low[nod] = min(low[nod], disc[x]); /// ne intoarcem in spate si actualizam low
        else
        {
            /// Mergem in fata
            st.push({nod, x});
            dfs(x, nod);

            low[nod] = min(low[nod], low[x]); /// cand mergem in fata actualizam low

            if(low[x] >= disc[nod]) /// daca gasim un punct critic
            {
                bcc++;

                while(!st.empty())
                {
                    comp[bcc].insert(st.top().first);
                    comp[bcc].insert(st.top().second);

                    if(st.top().first == nod && st.top().second == x)
                    {
                        st.pop();
                        break;
                    }

                    st.pop();
                }
            }
        }
    }
}

int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int t=1;
    //cin>>t;
    while(t--)
    {
        int n, m, a, b;
        cin>>n>>m;

        for(int i=0; i<m; i++)
        {
            cin>>a>>b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        dfs(1, 0);

        cout<<bcc<<'\n';
        for(int i=1; i<=bcc; i++)
        {
            //cout<<i<<"  ";
            for(auto x : comp[i])
                cout<<x<<" ";
            cout<<'\n';
        }
    }


    return 0;
}