Cod sursa(job #3373789)

Utilizator licadariaLica Daria licadaria Data 7 noiembrie 2026 21:49:00
Problema Componente biconexe Scor 58
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <iostream>
#include<vector>
#include<fstream>
#include <stack>
#include <utility>
using namespace std;

class nod {
public:
    vector<int> vecini;
    int vizitat = 0,niv, niv_min;
};
ofstream fout("biconex.out");
vector<nod> graf;
stack<pair<int, int>> stiva;
vector<vector<int>> rez;
int nr_biconexe=0, N, M;
void df(int i) {
    graf[i].vizitat = 1;
    graf[i].niv_min = graf[i].niv;
    for (auto j: graf[i].vecini) {
        if (graf[j].vizitat==0) {
            stiva.push({i,j});
            graf[j].niv = graf[i].niv+1;
            df(j);
            graf[i].niv_min = min(graf[i].niv_min, graf[j].niv_min);
            if (graf[j].niv_min>=graf[i].niv) {
                int a,b;
                nr_biconexe++;
                a = stiva.top().first;
                b = stiva.top().second;
                stiva.pop();
                if (a==i && b==j) {
                    rez[nr_biconexe].push_back(a);
                    rez[nr_biconexe].push_back(b);
                }
                else {
                    rez[nr_biconexe].push_back(a);
                    do {
                        a = stiva.top().first;
                        b = stiva.top().second;
                        stiva.pop();
                        rez[nr_biconexe].push_back(a);
                    }while (a != i || b != j);
                }
            }
        }else if (graf[j].niv < graf[i].niv-1) {
            stiva.push({i,j});
            graf[i].niv_min = min(graf[i].niv_min, graf[j].niv);
        }
    }
}

int main() {
    ifstream fin("biconex.in");
    fin>>N>>M;
    int x,y;
    graf.resize(N+1);
    for (int i=0; i<M; i++) {
        fin>>x>>y;
        graf[x].vecini.push_back(y);
        graf[y].vecini.push_back(x);
    }

    fin.close();
    rez.resize(N+1);
    for (int i=1; i<=N; i++) {
        if (graf[i].vizitat==0) {
            graf[i].niv = 1;
            df(i);
        }
    }
    fout<<nr_biconexe<<endl;
    for (int i=1; i<=nr_biconexe; i++) {
        for (int j=0; j<rez[i].size(); j++) {
            fout<<rez[i][j]<<" ";
        }
        fout<<endl;
    }

    fout.close();

}