Cod sursa(job #3374255)

Utilizator daria_staminStamin Daria Alexandra daria_stamin Data 8 noiembrie 2026 21:21:01
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int MAXN = 100005;

vector<pair<int, int>> g[MAXN];
vector<vector<int>> componente;

int nivel[MAXN], low[MAXN], parent[MAXN];
int muchieParinte[MAXN], poz[MAXN];
int n, m, timerDFS = 0;

vector<pair<int, int>> stivaMuchii;

void componenta(int x, int y) {
    vector<int> comp;

    while (!stivaMuchii.empty()) {
        auto e = stivaMuchii.back();
        stivaMuchii.pop_back();

        comp.push_back(e.first);
        comp.push_back(e.second);

        if (e.first == x && e.second == y)
            break;
    }

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

    componente.push_back(comp);
}

void DFS(int start) {
    vector<int> stiva;
    stiva.push_back(start);

    nivel[start] = low[start] = ++timerDFS;

    while (!stiva.empty()) {
        int x = stiva.back();

        if (poz[x] == (int)g[x].size()) {
            stiva.pop_back();

            if (parent[x] != 0) {
                int p = parent[x];

                low[p] = min(low[p], low[x]);

                if (low[x] >= nivel[p])
                    componenta(p, x);
            }

            continue;
        }

        auto [y, id] = g[x][poz[x]++];

        if (id == muchieParinte[x])
            continue;

        if (nivel[y] == 0) {
            parent[y] = x;
            muchieParinte[y] = id;

            stivaMuchii.push_back({x, y});

            nivel[y] = low[y] = ++timerDFS;
            stiva.push_back(y);
        }
        else if (nivel[y] < nivel[x]) {
            low[x] = min(low[x], nivel[y]);
            stivaMuchii.push_back({x, y});
        }
    }
}

int main() {
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;

        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }

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

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

    for (auto comp : componente) {
        for (int x : comp)
            fout << x << ' ';
        fout << '\n';
    }

    return 0;
}
//
// Created by daria on 11/8/2026.
//