Cod sursa(job #3225612)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 18 aprilie 2024 10:11:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

#define MAX_N 100000

const int INF = 1e9;

int n, m, cnt;
bitset < MAX_N + 1> viz;
stack <int> st;
vector <int> low, parent, h;
vector <vector <int> > graph, components;

void dfs(int node)
{
    st.push(node);
    viz[node] = 1;
    h[node] = h[parent[node]] + 1;
    low[node] = h[node];
    /*  low[node] = cel mai inalt nivel la carepputem ajunge
        dintr un nod din subarborele lui node printr -o
        SINGURA muchie de intoarcere
    */
    for(const int &x : graph[node])
    {
        if(viz[x])
        {
            if(x != parent[node])
                low[node] = min(low[node], h[x]);
        }
        else
        {
            parent[x] = node;
            dfs(x);
            low[node] = min(low[node], low[x]);
            if(low[x] >= h[node])
            {
                ++cnt;
                while(!st.empty()  &&  st.top() != x)
                {
                    components[cnt].push_back(st.top());
                    st.pop();
                }
                st.pop();
                components[cnt].push_back(x);
                components[cnt].push_back(node);
            }
        }
    }

}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    cin >> n >> m;
    graph.resize(n + 1);

    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    low.resize(n + 1, INF);
    parent.resize(n + 1);
    h.resize(n + 1);
    components.resize(n + 1);

    dfs(1);


    cout << cnt << "\n";
    for(int i = 1; i <= cnt; i ++)
    {
        for(const int &x : components[i])
            cout << x << " ";
        cout << "\n";
    }
    return 0;
}