Cod sursa(job #2796542)

Utilizator gabrielanideleaNidelea Gabriela-Andreea gabrielanidelea Data 8 noiembrie 2021 13:53:42
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.98 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<stack>
#include<vector>
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

class graf{
public:
    //bfs - declarari
    //int N, M, S, vizitat[100010], minime[100010];
    //vector<int> stocare[100010];
    //queue<pair<int, int>> coada;

    //dfs - declarari
   // int N, M;
    //vector<vector<int>> D;
    //vector<int>ok; //pt a marca nodul ca vizitat sau nu - 0 sau 1
   // graf(){}


    //BFS
   // void bfs(int start)
   // {
       // pair<int, int> curent;
       // coada.push({start, 0}); // dist de la start la el insusi e 0
       // minime[start] = 0; // momentan, minime va avea val 0
       // vizitat[start] = 1; // vizitez nodul curent
        //while(!coada.empty())
        //{
          //  curent = coada.front();
          //  minime[curent.first] = curent.second;
          //  coada.pop();
           // for(auto i : stocare[curent.first]) // parcurgem primele elem din pereche
           //     if(!vizitat[i]){
            //        coada.push({i, curent.second+1}); //cresc contorul
            //        vizitat[i] = 1; // vizitez nodul i
             //   }
       // }

   // }
   // void creare_graf(int N, int M, int S)
   // {
    //    this-> N = N;
     //   this-> M = M;
     //   this-> S = S;
      //  for(int i = 0; i< 100010; i++)
    //            minime[i] = -1; //umplem tabl de dist minime cu -1
   // }
  //  void creare_adiacente(int M)
    //{
       // int nod1, nod2;
       // for(int i = 1; i<= M; i++)
       // {
       //     f>>nod1>>nod2;
        //    stocare[nod1].push_back(nod2);
       // }

   // }
    //


    //DFS
    /*
    void dfs(int start)
    {
        ok[start] = 1;
        for(auto i: D[start]) // parcurg D
            if(ok[i]==0)
            {
                ok[i] =1;
                dfs(i);
            }


    }
    void creare_graf_Dfs(int N, int M)
    {
        this-> N = N;
        this -> M =M;
        ok=vector<int>(N+1);
        D=vector<vector<int>>(N+1);


    }
    void creare_adiacente_Dfs(int M)
    {
         int nod1, nod2;
         for(int i = 1; i<= M; i++)
        {
            f>>nod1>>nod2;
            D[nod1].push_back(nod2);
            D[nod2].push_back(nod1);
        }

    }
    int comp_conexe(int N)
    {
        int k= 0;
        for(int i =1; i<= N; i++)
            if(ok[i]==0)
            {
                k++;
                dfs(i);
            }
        return k;
    }
    */
    //biconex declarari
    int N, M, z, d[100001], l[100001];
    stack<pair<int, int>> st; //stiva fol first si second
    vector<vector<int>> D;
    vector<vector<int>> rez; //vectorul pt rezultate biconex
    graf(){}
    void bic(int x, int y)
    {
        vector<int>vect;
        while(st.top().first!=x && st.top().second!=y) //parcurg cat timp first e dif de nod1 si second e dif de nod2
        {
            vect.push_back(st.top().second); //retinem in vect nodul in care aj
            st.pop(); // in scoatem din stiva
        }
        vect.push_back(y); //adaugam nod2 in vect
        vect.push_back(x); //adaug nod1 in vect
        st.pop(); //scoatem din stiva ultimul nod ramas
        rez.push_back(vect); //tin minte nodurile marcate din vect cu aj lui rez

    }
    void dfsbic(int nod_curent)
    {
        d[nod_curent]=++z;
        l[nod_curent]=z;
        for(auto iter: D[nod_curent])
        {
            if(d[nod_curent]!=0)
            {
                l[nod_curent] = min(d[iter], l[nod_curent]) ; //pastram minimul
            }
            else
            {
                st.push({nod_curent, iter}); //adaug ca pereche in stiva nodul curent i si unde am ajuns cu unde am ajuns cu iteratorul
                dfsbic(iter); //apelam recursiv dfsbic pt fiecare nod nemarcat
                l[nod_curent]=min(l[nod_curent], l[iter]);
                if(d[nod_curent]<=l[iter]) bic(nod_curent, iter);
            }
        }
    }

    void creare_adiacente_bic(int M)
    {
         int nod1, nod2;
         for(int i = 1; i<= M; i++)
        {
            f>>nod1>>nod2;
            D[nod1].push_back(nod2);
            D[nod2].push_back(nod1);
        }

    }



};
graf Gr;

int main()
{
    //BFS
    //int N, M, S;
    //f>>N>>M>>S;
    //Gr.creare_graf(N, M, S);
   // Gr.creare_adiacente(M);
    //Gr.bfs(S);
    //for(int i = 1; i<=N; i++)
       // g<< Gr.minime[i]<<" ";

    //DFS
    //int N, M;
   // f>>N>>M;
    //Gr.creare_graf_Dfs(N, M);
    //Gr.creare_adiacente_Dfs(M);
    //g<<Gr.comp_conexe(N);

    //Comp Biconexe
    int N, M;
    f>>N>>M;
    //Gr.creare_graf_bic(N, M);
    Gr.creare_adiacente_bic(M);
    Gr.dfsbic(1);
    g<<Gr.rez.size()<<endl;
    for(int i=0; i<Gr.rez.size(); i++)
    {
        for(int j=0; j<Gr.rez.size(); j++)
            g<<Gr.rez[i][j]<<" ";
       g<<endl;

    }

    return 0;

}