Cod sursa(job #3373368)

Utilizator alexandra8Bratan Alexandra alexandra8 Data 6 noiembrie 2026 18:10:42
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include<vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,nr=0;
vector<vector<int>>adj;
vector<int>ctr;
vector<int>niv;
stack<pair<int,int>> st;
vector<vector<int>>componente;
vector<int>noduri_cmp;


void DFS(int nod, int parinte) {
    ctr[nod]=niv[nod]=++nr;
    for (int i: adj[nod]) {
        if (i!=parinte) {
            if (ctr[i]==0) {
                st.push({nod, i});
                DFS(i,nod);
                niv[nod] = min(niv[nod], niv[i]);

                if (niv[i] >= ctr[nod]) {
                    noduri_cmp.clear();
                    while (st.top() != make_pair(nod,i)) {
                        auto muchie=st.top();
                        st.pop();
                        noduri_cmp.push_back(muchie.first);
                        noduri_cmp.push_back(muchie.second);
                    }
                    st.pop();
                    noduri_cmp.push_back(nod);
                    noduri_cmp.push_back(i);
                    componente.push_back(noduri_cmp);
                }
            }
            else{
                niv[nod] = min(niv[nod], ctr[i]);
                st.push({nod, i});
            }
        }
        }

}
int main()
{

    fin>>n>>m;
    adj.resize(n+5);
    ctr.resize(n+5,0);
    niv.resize(n+5,0);
    for(int i=1; i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (!ctr[i]) {
            DFS(i, 0);
        }
    }

   fout<<componente.size();
    for (auto &comp : componente) {
        for (int x : comp) {
            fout<<x<< " ";
        }
        fout<<'\n';
    }


    return 0;
}