Cod sursa(job #3262864)

Utilizator solicasolica solica solica Data 11 decembrie 2024 19:39:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.53 kb
/*
  ____   ___  _     ___ ____    _
 / ___| / _ \| |   |_ _/ ___|  / \
 \___ \| | | | |    | | |     / _ \
  ___) | |_| | |___ | | |___ / ___ \
 |____/ \___/|_____|___\____/_/   \_\

*/
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define int long long int
#define pii pair<int,int>

const int NMAX = 2e5+9;

const int MOD = 1e9+7;

int binpow(int n, int k)
{
    if (k==0)
    {
        return 1;
    }
    int x=binpow(n,k/2)%MOD;
    if (k%2==0)
    {
        return x*x%MOD;
    }
    else
    {
        return x*x%MOD*n%MOD;
    }
}

ifstream fin ("biconex.in");
ofstream fout ("biconex.out");

#define cin fin
#define cout fout

vector<int>g[NMAX],comp[NMAX];

int n,m,i,j,bcc;

stack<int>s;/// folosesc o stiva pentru determinarea componentelor biconexe

/// daca la un moment dat am gasit nodul node ca fiind puncte de articulatie, golesc stiva pana la it inclusiv, aceste noduri impreuna cu node formand o componenta biconexa

int nma[NMAX];/// nivelul minim accesibil dintr-un nod x prin muchii din arborele dfs si dupa printr-o muchie de intoarcere

int depth[NMAX];//depth-ul nodului x in dfs tree

bool viz[NMAX];

void dfs (int node, int parent=0)
{
    viz[node]=1;
    nma[node]=depth[node]=depth[parent]+1;///se initializeaza cu depth-ul nodului curent
    s.push (node);
    for (auto it : g[node])
    {
        if (viz[it])
        {
            nma[node]=min(nma[node],depth[it]);/// cazul in care ma intorc
        }
        else
        {
            dfs(it,node);
            nma[node]=min(nma[node],nma[it]);
            if (nma[it]>=depth[node])/// node este punct de articulatie
            {
                bcc++;
                while (!s.empty () && s.top()!=it)
                {
                    comp[bcc].pb(s.top());
                    s.pop();
                }
                comp[bcc].pb(s.top());
                s.pop();
                comp[bcc].pb(node);
            }
        }
    }
}

void run_case ()
{
    cin>>n>>m;
    for (i=1; i<=m; i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].pb(b),g[b].pb(a);
    }
    dfs(1);
    cout<<bcc<<'\n';
    for (i=1; i<=bcc; i++)
    {
        sort (comp[i].begin(),comp[i].end());
        for (auto nod : comp[i])
        {
            cout<<nod<<' ';
        }
        cout<<'\n';
    }
}

signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL),cout.tie ();
    int teste=1;
    while (teste--)
    {
        run_case();
    }
}