Cod sursa(job #3183186)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 10 decembrie 2023 21:55:07
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100005;

vector<int> g[NMAX];
int n, m, tin[NMAX], low[NMAX], timer;
bool vis[NMAX];
int nr_comp;
vector<int> comp[NMAX];
stack<int> st;

void dfs(int curr, int prv = -1) {
    vis[curr] = true;
    tin[curr] = low[curr] = ++timer;
    st.push(curr);

    for (auto nxt : g[curr]) {
        if (nxt == prv)
            continue;

        if (vis[nxt]) { // back edge
            low[curr] = min(low[curr], tin[nxt]);
        } else {
            dfs(nxt, curr);
            low[curr] = min(low[curr], low[nxt]);

            if (low[nxt] >= tin[curr]) { // bridge

                nr_comp++;
                while (!st.empty() && st.top() != nxt) {
                    comp[nr_comp].push_back(st.top());
                    st.pop();
                }
                if (!st.empty()) {
                    comp[nr_comp].push_back(st.top());
                    st.pop();
                }
                comp[nr_comp].push_back(curr);

            }
        }
    }
}

int main() {

    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1);

    fout << nr_comp << '\n';
    for (int i = 1; i <= nr_comp; i++) {
        for (auto x : comp[i]) {
            fout << x << ' ';
        }
        fout << '\n';
    }

    return 0;
}