Cod sursa(job #3346669)

Utilizator parrot279Sofi Tudose parrot279 Data 14 martie 2026 21:07:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nmax = 1e5+5;
void dfs(int nod, int tata);

int n, m, nrcomp, tint[nmax], tmin[nmax];
bool viz[nmax];
vector<int> adj[nmax], sol[nmax];
stack<int> s;

int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1, 0);
    fout<<nrcomp<<"\n";
    for(int i = 1; i <= nrcomp; ++i)
    {
        for(auto nod : sol[i])
            fout<<nod<<" ";
        fout<<"\n";
    }

    return 0;
}

void dfs(int nod, int tata)
{
    tint[nod] = tint[tata] + 1;
    tmin[nod] = tint[nod];
    viz[nod] = 1;
    s.push(nod);
    for(auto i : adj[nod])
    {
        if(i == tata)
            continue;
        if(viz[i])
            tmin[nod] = min(tmin[nod], tint[i]);
        else
        {
            dfs(i, nod);
            tmin[nod] = min({tmin[nod], tmin[i]});
            if(tint[nod] <= tmin[i])
            {
                ++nrcomp;
                while(s.top() != i)
                {
                    sol[nrcomp].push_back(s.top());
                    s.pop();
                }
                sol[nrcomp].push_back(i);
                s.pop();
                sol[nrcomp].push_back(nod);
            }
        }
    }
}