Cod sursa(job #3374943)

Utilizator GabrielPetrePetre Gabriel GabrielPetre Data 9 noiembrie 2026 19:55:07
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>

using namespace std;

class InParser {
private:
    FILE* fin;
    char* buff;
    int sp;
public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[32768]();
        sp = 32767;
    }
    ~InParser() {
        fclose(fin);
        delete[] buff;
    }
    InParser& operator >> (int& n) {
        char c;
        while (!isdigit(c = read_ch()));
        n = c - '0';
        while (isdigit(c = read_ch())) {
            n = n * 10 + c - '0';
        }
        return *this;
    }
private:
    char read_ch() {
        ++sp;
        if (sp == 32768) {
            sp = 0;
            fread(buff, 1, 32768, fin);
        }
        return buff[sp];
    }
};

const int MAXN = 100005;
vector<int> adj[MAXN];
int tin[MAXN], low[MAXN], timer;
stack<int> st;
vector<vector<int>> bcc;

void dfs(int u, int p = -1) {
    tin[u] = low[u] = ++timer;
    st.push(u);

    for (int v : adj[u]) {
        if (v == p) continue;

        if (tin[v]) {
            low[u] = min(low[u], tin[v]);
        }
        else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] >= tin[u]) {
                vector<int> current_bcc;
                int node;
                do {
                    node = st.top();
                    st.pop();
                    current_bcc.push_back(node);
                } while (node != v);
                current_bcc.push_back(u);
                bcc.push_back(current_bcc);
            }
        }
    }
}

int main() {
    InParser fin("biconex.in");
    FILE* fout = fopen("biconex.out", "w");

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

    for (int i = 0; i < m; ++i) {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i) {
        if (!tin[i]) {
            dfs(i);
        }
    }

    fprintf(fout, "%zu\n", bcc.size());
    for (const auto& comp : bcc) {
        for (int node : comp) {
            fprintf(fout, "%d ", node);
        }
        fprintf(fout, "\n");
    }

    fclose(fout);
    return 0;
}