Cod sursa(job #3029993)

Utilizator VladS23Vlad Seba VladS23 Data 17 martie 2023 12:51:48
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

const int NMAX = 1e5;

int n, m;
vector<vector<int>> edges;
vector<set<int>> ans;

int low[NMAX + 5], dpth[NMAX + 5];

stack<pair<int, int>> st;

void cache(int x, int y)
{
    set<int> aux;
    int tx, ty;
    do
    {
        tx = st.top().first;
        ty = st.top().second;
        aux.insert(tx);
        aux.insert(ty);
        st.pop();
    }
    while(tx != x || ty != y);

    ans.push_back(aux);
}

void DFS(int node, int parent, int depth)
{
    dpth[node] = depth;
    low[node] = depth;

    for (auto it : edges[node])
    {
        if (it == parent)
            continue;
        if (!dpth[it])
        {
            st.push({node, it});
            DFS(it, node, depth + 1);
            low[node] = min(low[node], low[it]);
            if (low[it] >= dpth[node])
            {
                cache(node, it);
            }
        }
        else
            low[node] = min(low[node], low[it]);
    }
}

int main()
{
    cin >> n >> m;
    edges.resize(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    DFS(1, 0, 1);
    cout << ans.size() << '\n';
    for (auto it : ans)
    {
        for (auto jt : it)
            cout << jt << ' ';
        cout << '\n';
    }
    return 0;
}