Cod sursa(job #2798793)

Utilizator AndreeaCreitaCreita Andreea AndreeaCreita Data 11 noiembrie 2021 21:32:55
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.52 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
vector<int>g[100005];
int low[100005];
int lvl[1000005];
vector<pair<int,int>> critice;
vector<pair<int,int>> mch_elim;
vector<vector<int>> comp_biconexe;
int vecin,nodCurent,lv,nrNoduri,nrMuchii;

ifstream in("biconexe.in");
ofstream out("biconexe.out");
void dfs(int nodCurent, int parinte, int l)
{
    lvl[nodCurent]=l;
    low[nodCurent]=l;
    for(auto vecin : g[nodCurent])
    {
        if(lvl[vecin]==0)
        {
            dfs(vecin,nodCurent,l+1);
            low[nodCurent]=min(low[nodCurent],low[vecin]);

        }
        else if(vecin!=parinte)
        {
            low[nodCurent]=min(low[nodCurent],lvl[vecin]);
        }
    }
    if(low[nodCurent]==lvl[nodCurent]&& parinte!=-1)
    {
        critice.push_back({nodCurent,parinte});
    }
}

void eliminare_muchii_critice()
{

    for(auto& per:critice)
    {
     int from, to;
     from = per.first;
     to=per.second;

     g[from].erase(find(g[from].begin(),g[from].end(), to));
     g[to].erase(find(g[to].begin(),g[to].end(),from));


    }
}

void dfs2(int s)
{
    lvl[s] = 1;
    comp_biconexe[comp_biconexe.size()-1].push_back(s);
    for(auto el:g[s])
    {
        if(lvl[el]==0)
        {
            dfs2(el);
        }
    }
}

int main()
{
    in>>nrNoduri>>nrMuchii;

   int x,y;
    for(int i =0; i<nrMuchii; i++)
    {
        in>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,-1,1);
    for(auto& per:critice)
    {
        vector <int> comp_biconexa;         //punem in vectorul de int primul si al doilea elem din critice
        comp_biconexa.push_back(per.first);
        comp_biconexa.push_back(per.second);
        comp_biconexe.push_back(comp_biconexa); // punem in vectorul de vector componentele biconexe
    }


    eliminare_muchii_critice();
    for(int i=1; i<=nrNoduri; i++)
    {
        lvl[i]=0;                            //resetare vector lvl folosit ca viz
    }

    for(int i=1;i<=nrNoduri; i++)
    {
        if(lvl[i]==0)
        {
            comp_biconexe.push_back(vector<int> ());
            dfs2(i);
            if(comp_biconexe[comp_biconexe.size()-1].size()==1)
            {
                comp_biconexe.pop_back();
            }
        }
    }
    out<<comp_biconexe.size()<<'\n';
    for(auto& el:comp_biconexe)
    {
        for(auto& elem:el)
        {
             out<<elem<<' ';

        }
        out<<'\n';

    }


    return 0;
}