Cod sursa(job #2900565)

Utilizator mateicalin2002Ceausu Matei Calin mateicalin2002 Data 11 mai 2022 10:51:39
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
 
using namespace std;
 
const int NMAX = 1e5 + 5;

vector <int> e[NMAX],ans[NMAX];
stack <int> st;

int f[NMAX], p[NMAX];
int cnt = 0;
 
void dfs(int node) {
    p[node] = f[node];
    for (int i = 0;i < e[node].size();i++) {
        if (!f[e[node][i]]) {
            int s = st.size();
            f[e[node][i]] = f[node] + 1;
            dfs(e[node][i]);
            if (p[e[node][i]] >= f[node]) {
                while (st.size() > s) {
                    ans[cnt].push_back(st.top());
                    st.pop();
                }
                ans[cnt].push_back(node);
                cnt++;
            }
            p[node] = min(p[node], p[e[node][i]]);
        }
        p[node] = min(p[node], f[e[node][i]]);
    }
    st.push(node);
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    int n, m, a, b;
    cin >> n >> m;
    for (int j = 0; j < m; j++) {
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
        if (!f[i]) {
            f[i] = 1;
            dfs(i);
        }
    cout << cnt << '\n';
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < ans[i].size(); j++)
            cout << ans[i][j] << " ";
        cout << '\n';
    }
    return 0;
}