Cod sursa(job #3198640)

Utilizator UengineDavid Enachescu Uengine Data 29 ianuarie 2024 22:14:16
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

const int N = 1e5;

stack <int> stiva;
vector <vector<int>> graph, componente;
int highest[N + 5], depth[N + 5];


void dfs(int node, int nivel){
    stiva.push(node);
    highest[node] = depth[node] = nivel;
    for(auto vec:graph[node]){
        if(!depth[vec]){
            dfs(vec, nivel + 1);
            highest[node] = min(highest[vec], highest[node]);
            if(highest[vec] >= nivel) {
                vector <int> comp;
                while(!stiva.empty() and stiva.top() != vec) {
                    comp.push_back(stiva.top());
                    stiva.pop();
                }
                comp.push_back(stiva.top());
                stiva.pop();
                comp.push_back(node);
                componente.push_back(comp);
            }
        }
        else
            highest[node] = min(highest[node], depth[vec]);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n + 5);
    for(auto i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for( int i = 1; i <= n; i++ )
        if(!depth[i])
            dfs(i, 1);
    cout << componente.size() << "\n";
    for(auto &comp : componente){
        for(auto &node: comp)
            cout << node << " ";
        cout << "\n";
    }
    return 0;
}