Cod sursa(job #2811745)

Utilizator TeodorMarciucMarciuc Teodor TeodorMarciuc Data 3 decembrie 2021 00:19:08
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include<iostream>
#include<vector>
#include<stack>
#include<fstream>
#include<algorithm>
using namespace std;
int n, m, i, j, x, y, low[1000005], dfn[10000005], cnt;
vector<vector<int>>mu, ans;
stack<pair<int, int>>st;
void solve(int x, int y) {
    while (st.top().first != x and st.top().second != y) {
        ans[cnt].emplace_back(st.top().first);
        ans[cnt].emplace_back(st.top().second);
        st.pop();
    }
    ans[cnt].emplace_back(x);
    ans[cnt].emplace_back(y);
    st.pop();
    cnt++;
}
void DFS(int nod, int back, int number) {
    low[nod] = dfn[nod] = number;
    for (auto k : mu[nod]) {
        if (k == back) continue;
        if (dfn[k] == -1) {
            st.push({ nod,k });
            DFS(k, nod, number + 1);
            low[nod] = min(low[k], low[nod]);
            if (low[k] >= dfn[nod]) solve(nod, k);
        }
        else low[nod] = min(low[k], low[nod]);
    }
}
int main()
{
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    cin >> n >> m;
    mu.resize(m + 1);
    ans.resize(n + 1);
    for (i = 1;i <= m;i++)
    {
        cin >> x >> y;
        dfn[i] = -1;
        mu[x].emplace_back(y);
        mu[y].emplace_back(x);
    }
    DFS(1, 0, 1);
    cout << cnt << '\n';
    for (i = 0;i < cnt;i++) {
        sort(ans[i].begin(), ans[i].end());
        ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
        for (auto k : ans[i])
            cout << k << " ";
        cout << '\n';
    }
}