Cod sursa(job #3337180)

Utilizator stefanchpStefan Chiper stefanchp Data 26 ianuarie 2026 23:44:52
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector <int> g[100005];
vector <int> viz(100005, 0), niv(100005, 0), niv_min(100005, 0);
stack <int> s;
int nr_comp;
vector<int> comp[100005];

//  1 
// 2 5
// 3
// 4

void dfs(int nod)
{
    viz[nod] = 1;
    s.push(nod);
    niv_min[nod] = niv[nod];
    for(int i = 0; i < g[nod].size(); i++)
    {
        int vecin = g[nod][i];
        if(viz[vecin] == 0)
        {
            niv[vecin] = niv[nod] + 1;
            dfs(vecin);
            niv_min[nod] = min(niv_min[vecin], niv_min[nod]);
            if(niv_min[vecin] >= niv[nod])
            {
                //aici e muchia critica nod - vecin
                //punct critic 
                nr_comp++; 
                while(s.top() != vecin)
                {
                    comp[nr_comp].push_back(s.top());
                    s.pop();
                }
                comp[nr_comp].push_back(vecin);
                s.pop();
                comp[nr_comp].push_back(nod);
            }
        }
        else
        {
            if(niv[vecin] < niv[nod] - 1)
                niv_min[nod] = min(niv_min[nod], niv[vecin]);
        }
    }
}

int main()
{
    int x, y;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
    {
        if(viz[i] == 0)
        {
            niv[i] = 1;
            dfs(i);
        }
    }
    fout << nr_comp << '\n';
    for(int i = 1; i <= nr_comp; i++, fout << '\n')
        for(int j = 0; j < comp[i].size(); j++)
            fout << comp[i][j] << ' ';
    return 0;
}