Cod sursa(job #2716722)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 5 martie 2021 16:17:24
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
//
// Created by mihai145 on 05.03.2021.
//

#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 1e5;

int N, M;
vector <int> g[NMAX + 2];

vector<vector<int>> biconnectedComponents;

stack<int> st;
int _time, t[NMAX + 2], low[NMAX + 2];

void dfs(int node, int parent = -1) {
    st.push(node);

    _time++;
    t[node] = low[node] = _time;

    for(int son : g[node]) {
        if(son != parent) {
            if(t[son] != 0) {
                low[node] = min(low[node], t[son]);
                continue;
            }

            dfs(son, node);
            low[node] = min(low[node], low[son]);

            if(t[node] <= low[son]) {
                vector<int> comp;
                while(st.top() != node) {
                    comp.push_back(st.top());
                    st.pop();
                }
                comp.push_back(node);

                biconnectedComponents.push_back(comp);
            }
        }
    }
}

int main() {
    cin >> N >> M;

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

    dfs(1);

    cout << (int)biconnectedComponents.size() << '\n';

    for(vector<int> comp : biconnectedComponents) {
        for(int vertex : comp) {
            cout << vertex << ' ';
        }

        cout << '\n';
    }

    return 0;
}