Cod sursa(job #3374528)

Utilizator teosimSimzianu Teodora teosim Data 9 noiembrie 2026 01:47:36
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

vector<int> graf[100001];
vector<vector<int>> componente;
stack<int> stiva;
int nivel[100001];
int nivelMinim[100001];
int timp;

void dfs(int nod,int tata)
{
    timp++;
    nivel[nod]=timp;
    nivelMinim[nod]=timp;
    stiva.push(nod);

    for (int i=0;i<graf[nod].size();i++)
    {
        int vecin=graf[nod][i];
        if (vecin==tata)
            continue;

        if (nivel[vecin]==0)
        {
            dfs(vecin,nod);
            if (nivelMinim[vecin]<nivelMinim[nod])
                nivelMinim[nod]=nivelMinim[vecin];

            if (nivelMinim[vecin]>=nivel[nod])
            {
                vector<int> componenta;
                while (stiva.top()!=vecin)
                {
                    componenta.push_back(stiva.top());
                    stiva.pop();
                }
                componenta.push_back(vecin);
                stiva.pop();
                componenta.push_back(nod);
                componente.push_back(componenta);
            }
        }
        else if (nivel[vecin]<nivelMinim[nod])
            nivelMinim[nod]=nivel[vecin];
    }
}

int main()
{
    int n,m;
    fin>>n>>m;

    for (int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    for (int i=1;i<=n;i++)
    {
        if (nivel[i]==0)
        {
            dfs(i,0);
            stiva.pop();
        }
    }

    fout<<componente.size()<<"\n";
    for (int i=0;i<componente.size();i++)
    {
        for (int j=0;j<componente[i].size();j++)
            fout<<componente[i][j]<<" ";
        fout<<"\n";
    }

    return 0;
}