Cod sursa(job #2811678)

Utilizator VipioanaMirea Oana Teodora Vipioana Data 2 decembrie 2021 20:57:39
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int N=1e5+1;
int n,m,t[N],t_min[N],timp,n_cbc;
vector <int> a[N],cbc[N];
stack<pair<int,int>> stiva;
void adauga_cbc(pair<int,int> e)
{
    vector <int> comp;
    while(stiva.top().first!=e.first || stiva.top().second!=e.second)
    {
        comp.push_back(stiva.top().first);
        comp.push_back(stiva.top().second);
        stiva.pop();
    }
    comp.push_back(stiva.top().first);
    comp.push_back(stiva.top().second);
    stiva.pop();
    sort(comp.begin(),comp.end());
    n_cbc++;
    cbc[n_cbc].push_back(comp[0]);
    for(size_t i=1;i<comp.size();i++)
    {
        if(comp[i]!=comp[i-1])
        {
            cbc[n_cbc].push_back(comp[i]);
        }
    }
}

void dfs(int x,int tata)
{
    t_min[x]=t[x]=++timp;
    int nr_fii=0;
    for(auto y:a[x])
    {
        if(t[y]==0)
        {
            nr_fii++;
            stiva.push({x,y});
            dfs(y,x);
            t_min[x]=min(t_min[x],t_min[y]);
            if(t_min[y]>=t[x])
            {
                //p_art.push_back(x); ///x este pct de articulatie
                adauga_cbc({x,y});
            }
        }
        else
        if(y!=tata)
        {
            t_min[x]=min(t_min[x],t[y]);
        }
    }
    /*if(tata==0 && nr_fii>1)
    {
        p_art.push_back(x); ///x este pct de articulatie
    }*/
}
int main()
{
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    f.close();
    for(int i=1;i<=n;i++)
    {
        if(t[i]==0)
        {
            dfs(i,0);
        }
    }
    g<<n_cbc<<"\n";
    for(int i=1;i<=n_cbc;i++)
    {
        for(auto x:cbc[i])
        {
            g<<x<<" ";
        }
        g<<"\n";
    }
    return 0;
}