Cod sursa(job #3374149)

Utilizator CiulinAndreeaCiulin Andreea Iuliana CiulinAndreea Data 8 noiembrie 2026 19:17:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#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';
    }
}