Cod sursa(job #3349141)

Utilizator parrot279Sofi Tudose parrot279 Data 25 martie 2026 17:38:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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, cntbicon, tin[nmax], tmin[nmax];
bool viz[nmax];
vector<int> adj[nmax], bicon[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<<cntbicon<<"\n";
    for(int i = 1; i <= cntbicon; ++i)
    {
        for(auto nod : bicon[i])
            fout<<nod<<" ";
        fout<<"\n";
    }

    return 0;
}

void dfs(int nod, int tata)
{
    tin[nod] = tin[tata] + 1;
    tmin[nod] = tin[nod];
    viz[nod] = 1;
    s.push(nod);

    for(auto f : adj[nod])
    {
        if(f == tata)
            continue;

        if(viz[f])
            tmin[nod] = min(tmin[nod], tin[f]);
        else
        {
            dfs(f, nod);
            tmin[nod] = min(tmin[nod], tmin[f]);
            if(tin[nod] <= tmin[f])
            {
                ++cntbicon;
                while(s.top() != f)
                {
                    bicon[cntbicon].push_back(s.top());
                    s.pop();
                }
                s.pop();
                bicon[cntbicon].push_back(f);
                bicon[cntbicon].push_back(nod);
            }
        }
    }
}