Cod sursa(job #3348044)

Utilizator moloDaniMolodet Andrei Daniel moloDani Data 19 martie 2026 13:38:43
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int mxN = 1e5 + 1;

struct muchie{
    int u, v;
};

bool operator!=(muchie a, muchie b){
    return a.u != b.u || a.v != b.v;
}

int n, m;
vector<int> G[mxN], compBic[mxN];
int ord[mxN], low[mxN], ind = 0, noBic = 0;
stack<muchie> st;

void DFS(int nod, int parinte){
    ord[nod] = ++ind;
    low[nod] = ind;

    for(int x : G[nod]){
        if(!ord[x]){
            st.push({nod, x});
            DFS(x, nod);
            low[nod] = min(low[nod], low[x]);
            if(low[x] >= ord[nod]){
                noBic++;
                while(st.top() != (muchie){nod, x}){
                    muchie aux = st.top();
                    st.pop();
                    compBic[noBic].push_back(aux.u);
                    compBic[noBic].push_back(aux.v);
                }
                muchie aux = st.top();
                st.pop();
                compBic[noBic].push_back(aux.u);
                compBic[noBic].push_back(aux.v);
                sort(compBic[noBic].begin(), compBic[noBic].end());
                compBic[noBic].erase(unique(compBic[noBic].begin(), compBic[noBic].end()), compBic[noBic].end());
            }
        }else if(parinte != x && ord[x] < ord[nod]){
            st.push({x, nod});
            low[nod] = min(low[nod], ord[x]);
        }
    }
}

int main(){
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i = 1; i <= n; i++){
        if(!ord[i])
            DFS(i, 0);
    }

    fout << noBic << "\n";
    for(int i = 1; i <= noBic; i++){
        for(auto x : compBic[i])
            fout << x << " ";
        fout << "\n";
    }
}