Cod sursa(job #3372417)

Utilizator tudor120Dumitrache Tudor tudor120 Data 3 noiembrie 2026 19:03:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n,m,x,y,index[100001],low[100001],timp;
vector<int> graf[100001], componenta;
vector<vector<int>> componente;
stack<pair<int,int>> muchii;


void tarjan(int nod, int tata) {
    index[nod] = low[nod] = ++timp;

    for (int vecin : graf[nod]) {
        if (index[vecin] == 0) {
            muchii.push({nod, vecin});

            tarjan(vecin, nod);

            low[nod] = min(low[nod], low[vecin]);

            if (low[vecin] >= index[nod]) {
                componenta.clear();

                while (!muchii.empty()) {
                    int a = muchii.top().first;
                    int b = muchii.top().second;
                    muchii.pop();

                    componenta.push_back(a);
                    componenta.push_back(b);

                    if (a == nod && b == vecin)
                        break;
                }

                sort(componenta.begin(), componenta.end());
                componenta.erase(
                    unique(componenta.begin(), componenta.end()),
                    componenta.end()
                );

                componente.push_back(componenta);
            }
        }
        else if (vecin != tata && index[vecin] < index[nod]) {
            muchii.push({nod, vecin});
            low[nod] = min(low[nod], index[vecin]);
        }
    }
}


int main() {
    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 (index[i] == 0)
            tarjan(i, 0);
    }

    fout << componente.size() << '\n';

    for (auto comp : componente) {
        for (int nod : comp)
            fout << nod << " ";

        fout << '\n';
    }

    return 0;

}