Cod sursa(job #3219562)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 31 martie 2024 17:30:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#define MAXN 100000
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
int level[MAXN + 10], vis[MAXN + 10], minDepth[MAXN + 10], comp;
vector <int> graph[MAXN + 10], biconex[MAXN + 10], st;
void dfs(int node, int parent)
{
    st.push_back(node);
    level[node] = level[parent] + 1;
    minDepth[node] = level[node];
    vis[node] = 1;
    for (const auto &next : graph[node])
        if (next != parent)
        {
            if (vis[next] == 0)
            {
                dfs(next, node);
                minDepth[node] = min(minDepth[node], minDepth[next]);
                if (minDepth[next] >= level[node])
                {
                    comp++;
                    while (st.back() != next)
                    {
                        biconex[comp].push_back(st.back());
                        st.pop_back();
                    }
                    biconex[comp].push_back(st.back());
                    st.pop_back();
                    biconex[comp].push_back(node);
                }
            }
            else
                minDepth[node] = min(minDepth[node], level[next]);
        }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    dfs(1, 0);
    cout << comp << '\n';
    for (int i = 1; i <= comp; i++)
    {
        for (const auto &it : biconex[i])
            cout << it << ' ';
        cout << '\n';
    }
    return 0;
}