Cod sursa(job #2801609)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 16 noiembrie 2021 17:24:23
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

stack<pair<int, int>> st;
vector<int> gr[N], ans[N];
int niv[N], nr_con;

int dfs(int nod, int tata) {
    int niv_min = niv[nod];
    for (auto vec : gr[nod]) {
        if (vec == tata) continue;
        if (niv[vec] > niv[nod]) continue;
        st.push({nod, vec});
        if (niv[vec] == 0) {
            niv[vec] = 1 + niv[nod];
            int niv_min_crt = dfs(vec, nod);
            if (niv_min_crt >= niv[nod]) {
                while (!st.empty() && st.top() != make_pair(nod, vec) && st.top() != make_pair(vec, nod)) {
                    ans[nr_con].push_back(st.top().first);
                    ans[nr_con].push_back(st.top().second);
                    st.pop();
                }
                ans[nr_con].push_back(nod);
                ans[nr_con].push_back(vec);
                if (!st.empty())
                    st.pop();
                ++nr_con;
            }
            niv_min = min(niv_min_crt, niv_min);
        }
        niv_min = min(niv_min, niv[vec]);
    }
    return niv_min;
}

int main() {
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    int n, m;
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    cin.close();
    for (int i = 1; i <= n; ++i)
        if (niv[i] == 0) {
            niv[i] = 1;
            dfs(i, 0);
        }
    cout << nr_con << "\n";
    for (int i = 0; i < nr_con; ++i) {
        sort(ans[i].begin(), ans[i].end());
        ans[i].resize(distance(ans[i].begin(), unique(ans[i].begin(), ans[i].end())));
        for (auto j : ans[i])
            cout << j << " ";
        cout << "\n";
    }
    cout.close();
    return 0;
}