Cod sursa(job #3374245)

Utilizator CiulinAndreeaCiulin Andreea Iuliana CiulinAndreea Data 8 noiembrie 2026 21:10:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.43 kb
/*
Am construit graful neorientat folosind liste de adiacență, apoi am aplicat algoritmul Tarjan cu DFS pentru determinarea componentelor biconexe.
Am utilizat vectorii nivel și low pentru a reține nivelul fiecărui nod în arborele DFS și cel mai mic nivel la care se poate ajunge din subarborele său.
Am folosit o stivă în care am memorat muchiile parcurse, iar atunci când condiția low[vecin] >= nivel[nod] a fost îndeplinită, am extras muchiile corespunzătoare unei componente biconexe și am reținut nodurile acesteia, eliminând duplicatele.
La final, am afișat numărul componentelor biconexe și nodurile fiecărei componente.
Complexitate:O(N + M * log M)
 */
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;

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

vector<int> graf[100001];
bool vizitat[100001];
int nivel[100001], low[100001];
stack<pair<int,int>> st;
vector<vector<int>> componente;

void DFS(int nod, int tata) {
    vizitat[nod]=true;
    low[nod]=nivel[nod];

    for (auto vecin : graf[nod]) {
        if (!vizitat[vecin]) {
            st.push({nod,vecin});
            nivel[vecin] = nivel[nod] + 1;
            DFS(vecin,nod);
            low[nod]= min(low[nod],low[vecin]);
            if (low[vecin]>=nivel[nod]) {
                vector<int> comp;
                while (true) {
                    auto muchie=st.top();
                    st.pop();
                    comp.push_back(muchie.first);
                    comp.push_back(muchie.second);
                    if (muchie.first==nod && muchie.second==vecin)
                        break;
                    }
                sort(comp.begin(), comp.end());
                comp.erase(unique(comp.begin(), comp.end()), comp.end());
                componente.push_back(comp);

            }
        } else if (vecin!=tata && nivel[vecin]<nivel[nod]) {
            st.push({nod, vecin});
            low[nod]=min(low[nod], nivel[vecin]);
        }
    }
}

int main() {
    int n, m,x ,y;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    for (int i=1; i<=n; i++) {
        if (!vizitat[i]) {
            nivel[i]=1;
            DFS(i,0);
        }
    }
    fout<<componente.size()<< '\n';
    for (auto comp: componente) {
        for (auto nod: comp) {
            fout<<nod<< " ";
        }
        fout<< '\n';
    }
}