Cod sursa(job #3224840)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 16 aprilie 2024 12:33:47
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include<bits/stdc++.h>
using namespace std;

const int NMAX = 1e5 + 5;
int n, m, level[NMAX], low[NMAX], nrComp;
vector<int> v[NMAX], ans[NMAX]; 
bool viz[NMAX];
stack<int> s;

void dfs(int node, int tata)
{
    cerr << node << " ";
    level[node] = level[tata] + 1;
    low[node] = level[tata] + 1 ;
    viz[node] = 1;
    s.push(node);

    for(auto u : v[node])
    {
        if(u == tata)
            continue;
        if(viz[u])
            low[node] = min(low[node], level[u]);
        else
        {
            dfs(u, node);
            low[node] = min(low[node], low[u]);
            if(low[u] >= level[node])
            {
                nrComp++;
                while(s.top() != u)
                {
                    ans[nrComp].push_back(s.top());
                    s.pop();
                }
                ans[nrComp].push_back(u);
                s.pop();
                ans[nrComp].push_back(node);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

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

    dfs(1, 0);
    cout << nrComp << "\n";
    for(int i = 1; i <= nrComp; i++)
    {
        for(auto u : ans[i])
            cout << u << " ";
        cout << "\n";
    }
}