Cod sursa(job #2976514)

Utilizator razvanalexrotaruRazvan Alexandru Rotaru razvanalexrotaru Data 9 februarie 2023 13:26:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
#include <fstream>
#define cin fin
#define cout fout
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector<int>V,sol[100008],G[100008];
int a,b,i,nvl[100008],nvlmin[100008],n,m,cnt;
void dfs(int nod,int tata)
{
    nvl[nod]=nvl[tata]+1;
    nvlmin[nod]=nvl[nod];
    V.push_back(nod);
    for(auto i:G[nod])
    {
        if(i!=tata)
        {
            if(nvl[i]==0)
            {
                dfs(i,nod);
                nvlmin[nod]=min(nvlmin[nod],nvlmin[i]);
                if(nvl[nod]<=nvlmin[i])
                {
                    cnt++;
                    while(V.back()!=i)
                    {
                        sol[cnt].push_back(V.back());
                        V.pop_back();
                    }
                    sol[cnt].push_back(i);
                    sol[cnt].push_back(nod);
                    V.pop_back();
                }
            }
            else
            {
                nvlmin[nod]=min(nvlmin[nod],nvl[i]);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0);
    cout<<cnt<<'\n';
    for(i=1;i<=cnt;i++)
    {
        for(auto j:sol[i])
            cout<<j<<" ";
        cout<<'\n';
    }
    return 0;
}