Cod sursa(job #3374722)

Utilizator Iulian.CorobanCoroban Silviu Iulian Iulian.Coroban Data 9 noiembrie 2026 09:44:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <fstream>
#include <vector>

using namespace std;

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

int N, M;
vector<int> graf[100005];
int nivel[100005];
int nivelMinim[100005];
bool vizitat[100005];
int timpCurent;
vector<int> stiva;
vector<vector<int>> componente;

void citire()
{
    fin >> N >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int u, v;
        fin >> u >> v;
        
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
}

void dfs(int nod, int tata)
{
    vizitat[nod] = true;
    timpCurent = timpCurent + 1;
    nivel[nod] = timpCurent;
    nivelMinim[nod] = timpCurent;
    
    stiva.push_back(nod);
    
    for(int vecin : graf[nod])
    {
        if(vecin != tata)
        {
            if(vizitat[vecin] == true)
            {
                if(nivel[vecin] < nivelMinim[nod])
                {
                    nivelMinim[nod] = nivel[vecin];
                }
            }
            else
            {
                dfs(vecin, nod);
                
                if(nivelMinim[vecin] < nivelMinim[nod])
                {
                    nivelMinim[nod] = nivelMinim[vecin];
                }
                
                if(nivelMinim[vecin] >= nivel[nod])
                {
                    vector<int> componentaCurenta;
                    bool gata = false;
                    
                    while(gata == false)
                    {
                        int ultimulNod = stiva.back();
                        stiva.pop_back();
                        componentaCurenta.push_back(ultimulNod);
                        
                        if(ultimulNod == vecin)
                        {
                            gata = true;
                        }
                    }
                    
                    componentaCurenta.push_back(nod);
                    componente.push_back(componentaCurenta);
                }
            }
        }
    }
}

int main()
{
    citire();
    
    for(int i = 1; i <= N; i++)
    {
        if(vizitat[i] == false)
        {
            dfs(i, 0);
        }
    }
    
    fout << componente.size() << "\n";
    
    for(vector<int> comp : componente)
    {
        for(int nod : comp)
        {
            fout << nod << " ";
        }
        
        fout << "\n";
    }
    
    return 0;
}