Cod sursa(job #3374065)

Utilizator mattiaslupuLupu Mattias Andrea mattiaslupu Data 8 noiembrie 2026 17:00:43
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m, nrComponente, timpCurent;
vector<int> vizitat, timp, low;
vector<vector<int>> lista;
stack<pair<int, int>> muchii;
vector<vector<int>> componente;

void dfs(int nod, int tata) {
    vizitat[nod]=1;
    timp[nod]=low[nod]=++timpCurent;
    for (int vecin : lista[nod]) {
        if (vecin==tata) {
            continue;
        }
        if (!vizitat[vecin]) {
            muchii.push({nod, vecin});
            dfs(vecin, nod);
            if (low[vecin]<low[nod]) {
                low[nod]=low[vecin];
            }
            if (low[vecin]>=timp[nod]) {
                vector<int> componenta;
                while (!muchii.empty()) {
                    int x=muchii.top().first;
                    int y=muchii.top().second;
                    muchii.pop();

                    componenta.push_back(x);
                    componenta.push_back(y);

                    if (x==nod&&y==vecin) {
                        break;
                    }
                }
                vector<int> noduriUnice;
                vector<int> adaugat(n+1, 0);

                for (int x:componenta) {
                    if (!adaugat[x]) {
                        adaugat[x]=1;
                        noduriUnice.push_back(x);
                    }
                }
                componente.push_back(noduriUnice);
                nrComponente++;
            }
        } else if (timp[vecin]<timp[nod]) {
            muchii.push({nod, vecin});
            if (timp[vecin]<low[nod]) {
                low[nod]=timp[vecin];
            }
        }
    }
}

int main() {
    f>>n>>m;
    lista.resize(n+1);
    vizitat.resize(n+1, 0);
    timp.resize(n+1, 0);
    low.resize(n+1, 0);
    for (int i=0; i<m; i++) {
        int x, y;
        f>>x>>y;
        lista[x].push_back(y);
        lista[y].push_back(x);
    }
    for (int i=1; i<=n; i++) {
        if (!vizitat[i]) {
            dfs(i, 0);
        }
    }
    g<<nrComponente<<'\n';
    for (vector<int> componenta : componente) {
        for (int nod : componenta) {
            g<<nod<<' ';
        }
        g<<'\n';
    }

    return 0;
}