Cod sursa(job #3225573)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 17 aprilie 2024 23:38:02
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 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 isBridge(int a, int b)
{
    cout << "isBridge\n";
    cout << a <<  " " << b << "\n";
}

void isCutpoint(int a)
{
    cout << "isCutpoint\n";
    cout << a << "\n";
}

void dfs(int node)
{
    st.push(node);
    viz[node] = 1;
    h[node] = h[parent[node]] + 1;
    low[node] = h[node];
//    cout << node << "\n";
//    cout << low[node] << " aa\n";
    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.top() != node)
                {
                    components[cnt].push_back(st.top());
                    st.pop();
                }
                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";
    }
//    for(int i = 1; i <= n; i ++)
//        cout << i << " " << low[i] <<"\n";
    return 0;
}