Cod sursa(job #2793519)

Utilizator monicaandreea46Girbea Monica monicaandreea46 Data 3 noiembrie 2021 18:29:52
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.06 kb
#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
#include<deque>
std::ifstream f("biconex.in");
std::ofstream fg("biconex.out");
int n, m, a, b;

class graf{
public:
    int n, m;

    graf(int n, int m);

    std::vector<std::vector<int> > lista;
    std::vector<std::set<int>> componente;
    std::vector<int> viz;
    std::vector<int> low;
    std::vector<int> tata;
    std::deque<int> st;
    std::deque<std::pair<int, int>> perechi;
    int nr_comp_biconex = 0;


    void new_lista( int nod1, int nod2);
    void dfs(int nod);
    void biconex();

};

graf::graf(int n, int m) {
    this->n = n;
    this->m = m;

    std::vector<int> v;
    for(auto i = 0 ; i<=n ; i++){
        viz.push_back(-1);
        low.push_back(-1);
        tata.push_back(-1);
        lista.push_back(v);
    }
}

void graf::new_lista(int nod1, int nod2){
    lista[nod1].push_back(nod2);
    lista[nod2].push_back(nod1);
}

void graf::dfs(int nod){
    static int cnt = 0;
    std::set<int> s;
    viz[nod] = ++cnt;
    low[nod] = cnt;
    st.push_back(nod);
    int nr_copii = 0;

    for( auto i = lista[nod].begin(); i != lista[nod].end(); i++) {
        if (viz[*i] == -1) {
            tata[*i] = nod;
            nr_copii++;
            perechi.push_back(std::make_pair(nod, *i));

            dfs(*i);

            low[nod] = fmin(low[nod], low[*i]);
          //  std::cout <<nod<<" si "<<*i<< "\n";
          //  std::cout <<viz[nod]<<" si "<<low[*i]<< "\n";

            if ( low[*i] >= viz[nod]) { //e punct de articulatie
                componente.push_back(s);

                while (perechi.back().first != nod || perechi.back().second != *i) {
                    componente[nr_comp_biconex].insert(perechi.back().first);
                    componente[nr_comp_biconex].insert(perechi.back().second);
                    //std::cout << perechi.back().first << " " << perechi.back().second << " ";
                    perechi.pop_back();
                }
                componente[nr_comp_biconex].insert(perechi.back().first);
                componente[nr_comp_biconex].insert(perechi.back().second);
                //std::cout << perechi.back().first << " " << perechi.back().second << " ";
                perechi.pop_back();

                ++nr_comp_biconex;

                //std::cout << "\n";
            }

        } else if (*i != tata[nod]) {
            low[nod] = fmin(low[nod], viz[*i]);
        }
    }

}

void graf::biconex(){

    for(int i = 0 ; i< n ; i++){
        if(viz[i] == -1) dfs(i);
    }

    std::cout<<nr_comp_biconex<<"\n";

    for(int i = 0 ; i<nr_comp_biconex ; i++){
        for(auto j = componente[i].begin() ; j != componente[i].end() ; j++)
            std::cout<< *j + 1<<" ";
        std::cout<<"\n";
    }


   /* std::cout<<"\n";
    for(int i=0 ; i<n ; i++)
        std::cout<<viz[i]<<" ";

    std::cout<<"\n";
    for(int i=0 ; i<n ; i++)
        std::cout<<low[i]<<" ";*/

}


int main() {
    f>>n>>m;

    graf g(n, m);
    for(int i=0 ; i<m ; i++){
        f>>a>>b;
        g.new_lista(a-1,b-1);
    }

    g.biconex();
    return 0;
}