Cod sursa(job #3373379)

Utilizator alexandra8Bratan Alexandra alexandra8 Data 6 noiembrie 2026 19:03:39
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 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;
vector<int> frecv;


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]);
                    noduri_cmp.clear();
                    if (niv[i] >= ctr[nod]) {
                        noduri_cmp.clear();
                        while (true) {
                            auto muchie = st.top();
                            st.pop();
                            if (frecv[muchie.first] == 0) {
                                noduri_cmp.push_back(muchie.first);
                                frecv[muchie.first] = 1;
                            }
                            if (frecv[muchie.second] == 0) {
                                noduri_cmp.push_back(muchie.second);
                                frecv[muchie.second] = 1;
                            }
                            if (muchie == make_pair(nod, i))
                                break;
                        }

                        componente.push_back(noduri_cmp);
                        for (int x : noduri_cmp) {
                            frecv[x] = 0;
                    }

                }
            }
            else if (ctr[i] < ctr[nod]){
                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);
    frecv.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()<<'\n';
    for (auto &comp : componente) {
        for (int x : comp) {
            fout<<x<< " ";
        }
        fout<<'\n';
    }


    return 0;
}