Cod sursa(job #2803363)

Utilizator ElizaTElla Rose ElizaT Data 19 noiembrie 2021 21:35:58
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;
vector <int> e[NMAX + 5],ans[NMAX + 5];
stack <int> st;
int f[NMAX + 5],p[NMAX + 5];
int cnt = 0;

int 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()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n,m,a,b;
    fin >> n >> m;
    for (int j = 0;j < m;j++) {
        fin >> 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);
        }
    fout << cnt << '\n';
    for (int i = 0;i < cnt;i++) {
        for (int j = 0;j < ans[i].size();j++)
            fout << ans[i][j] << " ";
        fout << '\n';
    }
    return 0;
}