Cod sursa(job #3296155)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 11 mai 2025 20:46:15
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> adj;

vector<int> depth;
vector<int> lowpoint;
stack<int> active;

vector<vector<int>> components;

void dfs(int v, int parent)
{
    lowpoint[v] = depth[v];
    active.push(v);

    for (int sz : adj[v]) {
        if (depth[sz] == -1) {
            depth[sz] = depth[v]+1;
            dfs(sz, v);

            lowpoint[v] = min(lowpoint[v], lowpoint[sz]);

            if (lowpoint[sz] >= depth[v]) {
                vector<int> comp;

                while (!active.empty() && active.top() != v) {
                    comp.push_back(active.top());
                    active.pop();
                }

                comp.push_back(v);
                components.push_back(comp);
            }
        }
        else if (sz != parent) {
            lowpoint[v] = min(lowpoint[v], depth[sz]);
        }
    }
}

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



    int n, m;
    fin >> n >> m;

    adj.resize(n+1);
    depth.resize(n+1, -1);
    lowpoint.resize(n+1, -1);

    for (int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }


    depth[1] = 0;
    dfs(1, -1);

    for (int i = 1; i <= n; i++)
        if (depth[i] == -1)
            fout << "not connected...\n";

    fout << components.size() << "\n";
    for (auto &c : components) {
        for (auto e : c) {
            fout << e << " ";
        }
        fout << "\n";
    }

    return 0;
}