Cod sursa(job #3293843)

Utilizator ShAwDoRneYNacu Gabriel ShAwDoRneY Data 12 aprilie 2025 18:42:48
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int N,M;
vector<bool> isVisited(100005, false);
vector<int> tin(100005);
vector<int> low(100005);
vector<vector<int>> graph(100005, vector<int>());
vector<vector<int>> compBiconexe;
stack<int> st;

int timer = 1;
int ans = 0;

void Articulation_Points(int node, int parent) {
    isVisited[node] = true;
    tin[node] = low[node] = timer++;
    st.push(node);

    for(auto neighbor : graph[node]) {
        if(neighbor == parent)
            continue;

        if(!isVisited[neighbor]) {
            Articulation_Points(neighbor, node);
            low[node] = min(low[node], low[neighbor]);

            if(low[neighbor] >= tin[node]) {
                ans++;
                vector<int> noduri;
                while(!st.empty() && st.top() != node) {
                    int x = st.top();
                    noduri.push_back(x);
                    st.pop();
                }
                noduri.push_back(node);
                compBiconexe.push_back(noduri);
            }
        }
        else {
            low[node] = min(low[node], tin[neighbor]);
        }
    }
}

int main() {

    fin >> N >> M;

    for(int i=1; i<=M; i++) {
        int x,y;
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    Articulation_Points(1, 0);

    fout << ans << "\n";

    for(auto vec : compBiconexe) {
        for(auto e : vec) {
            fout << e << ' ';
        }
        fout << "\n";
    }

    return 0;
}