Cod sursa(job #3373225)

Utilizator Teodor-CiprianNica Teodor-Ciprian Teodor-Ciprian Data 6 noiembrie 2026 13:03:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
void DFS(int nod,int tata,int nivel,const vector<vector<int>>& graf, vector<int>& niv, vector<int>& low, vector<int>& stiva, vector<vector<int>>& biconexe)
{
    niv[nod]=nivel;
    low[nod]=nivel;
    stiva.push_back(nod);
    for (int vecin:graf[nod])
    {
        if (vecin!=tata)
        {
            if(niv[vecin]!=0)
                low[nod]=min(low[nod],niv[vecin]);
            else
            {
                DFS(vecin,nod,nivel+1,graf,niv,low,stiva,biconexe);
                low[nod]=min(low[nod],low[vecin]);

                if (low[vecin]>=niv[nod])
                {
                    vector<int> comp;
                    int u;
                    do {
                        u = stiva.back();
                        stiva.pop_back();
                        comp.push_back(u);
                    } while (u!=vecin);
                    comp.push_back(nod);
                    biconexe.push_back(comp);
                }
            }
        }
    }
}

int main()
{
    int N, M;
    fin>>N>>M;

    vector<vector<int>> graf(N+1);
    vector<int> niv(N+1,0),low(N+1,0);
    vector<int> stiva;
    vector<vector<int>> biconexe;

    for (int c=0;c<M;c++)
    {
        int u,v;
        fin>>u>>v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }


    for(int i=1;i<=N;i++)
        if (niv[i]==0)
            DFS(i,0,1,graf,niv,low,stiva,biconexe);

    fout<<biconexe.size()<<'\n';
    for (auto i:biconexe)
    {
        for (auto j:i)
            fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}