Cod sursa(job #3373788)

Utilizator AndreiO86902462Andrei O AndreiO86902462 Data 7 noiembrie 2026 21:40:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

#define MAX_N 100000

vector<vector<int>> adj(MAX_N);
vector<int> disc(MAX_N, -1);
vector<int> low(MAX_N, -1);
vector<pair<int, int>> st;
vector<vector<int>> components;

int timer;

// https://www.geeksforgeeks.org/dsa/biconnected-components/
void dfs(int node, int parent = -1) {
    disc[node] = low[node] = timer; // disc doubles as a visited flag
    ++timer;
    
    int children = 0;

    for(int neighbor : adj[node]) {
        if(disc[neighbor] == -1) {
            children++;
            st.push_back({node, neighbor});
            dfs(neighbor, node);
            
            low[node] = min(low[node], low[neighbor]);
            
            if(low[neighbor] >= disc[node]) {
                vector<int> component = {};
                
                while(!st.empty()) {
                    pair<int,int> edge = st.back();
                    st.pop_back();
                    component.push_back(edge.first);
                    component.push_back(edge.second);
                    
                    if(edge.first == node && edge.second == neighbor)
                        break;
                }
                
                sort(component.begin(), component.end());
                component.erase(
                    unique(component.begin(), component.end()),
                    component.end()
                );
                components.push_back(component);
            }
                
        } else if(neighbor != parent && disc[neighbor] < disc[node]) { // back edge
            low[node] = min(low[node], disc[neighbor]);
            
            if(disc[node] < disc[neighbor]) {
                st.push_back({node, neighbor});
            }
        }
    }
}

int main()
{
    int n, m; fin >> n >> m;
    
    for(int i = 0; i < m; ++i) {
        int x, y; fin >> x >> y;
        --x; --y; // index from 0
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    vector<int> roots = {};
    
    st.push_back({});
    
    for(int i = 0; i < n; ++i)
        if(disc[i] == -1) 
            dfs(i);
    
    fout << components.size() << '\n';
    
    for(vector<int> component: components) {
        for(int vertex : component)
            fout << vertex + 1 << ' ';
        fout << '\n';
    }
    
    return 0;
}