Cod sursa(job #2803358)

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

using namespace std;

const int NMAX = 1e5;
vector <int> e[NMAX + 5],ans;
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.push_back(st.top());
                    st.pop();
                }
                ans.push_back(node);
                cnt++;
                ans.push_back(-1);
            }
            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 < ans.size();i++) {
        if (ans[i] == -1)
            fout << '\n';
        else
            fout << ans[i] << " ";
    }
    return 0;
}