Cod sursa(job #3333251)

Utilizator Victor5539Tanase Victor Victor5539 Data 12 ianuarie 2026 15:24:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>

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

const int NMAX=100000;
int n,i,viz[NMAX+5],order[NMAX+5],low[NMAX+5],node1,node2,sol,m;
vector <int> bcc[NMAX+5];
vector <int> adj[NMAX+5];
stack <int> st;

void dfs(int node, int daddy)
{
    viz[node]=1;

    if (daddy==-1)
        order[node]=1;
    else
        order[node]=order[daddy]+1;

    low[node]=order[node];

    st.push(node);

    for (auto node2: adj[node])
    {
        if (node2==daddy)
            continue;

        if (viz[node2]==1)
            low[node]=min(low[node],order[node2]);
        else
        {
            dfs(node2,node);

            low[node]=min(low[node],low[node2]);

            if (low[node2]>=order[node])
            {
                sol++;
                while (!st.empty() && st.top()!=node2)
                {
                    bcc[sol].push_back(st.top());
                    st.pop();
                }

                bcc[sol].push_back(node2);
                st.pop();
                bcc[sol].push_back(node);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr); fout.tie(nullptr);

    fin>>n>>m;
    while (m--)
    {
        fin>>node1>>node2;
        adj[node1].push_back(node2);
        adj[node2].push_back(node1);
    }


    for (i=1; i<=n; i++)
    {
        if (!viz[i])
            dfs(i,-1);
    }

    fout<<sol<<'\n';

    for (i=1; i<=sol; i++)
    {
        for (auto x: bcc[i])
            fout<<x<<" ";
        fout<<'\n';
    }
    return 0;
}