Cod sursa(job #2798527)

Utilizator pizzandreeaCiurescu Andreea pizzandreea Data 11 noiembrie 2021 14:51:51
Problema Componente biconexe Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.42 kb
#include <iostream>
#include <fstream>
#include <vector>

#define MAX 100001

using namespace std;
ifstream fin ("biconex.in");
ofstream fout("biconex.out");


vector <int> compBiconexe[MAX];

class Graf{
    public:
    //date membre
        vector <int> A[MAX];    //liste de adiacenta
        int mM, mN;
        int nrComp;     //nr comp conexe
        static bool viz[MAX];
        static int up[MAX];
        static int nivel[MAX];
        static int S[MAX];
        static int top;
        int nrCompBiconexe;

        //constructor

        Graf(int N, int M){
            mN = N;
            mM = M;
            nrComp = 0;
            nrCompBiconexe = 0;
        }

        void CitireGOrientat(){
            int x, y;

            for(int i = 1; i <= mM; i++){
                // citim muchiile
                fin >> x >> y;
                A[x].push_back(y);  //adaugam ambele noduri in lista celuilalt de adiacenta
                A[y].push_back(x);  //deoarece graful e neorientat
            }
        }
        void DFS(int start);
        void ComponenteConexe();


        void DFS_Biconex(int start, int father);
        void AfisareBiconex();

};



bool Graf :: viz[MAX] ={0};
int Graf :: up[MAX] = {0};
int Graf :: nivel[MAX] = {0};
int Graf :: S[MAX] = {0};
int Graf :: top = 0;

void Graf :: DFS (int start){
    viz[start] = 1;
    // vizitam nodul din care plecam

    for(int i = 0; i < A[start].size(); i++){
        // parcurgem toti vecinii nodului start
        if(!viz[A[start][i]] ){
            // daca nu am mai vizitat acest vecin
            DFS(A[start][i]);
        }
    }
}


void Graf :: ComponenteConexe(){
    
    for(int i = 1; i <= mN; i++){
        if(!viz[i]){
            nrComp++;
            DFS(i);
        }
    }
}


void Graf :: DFS_Biconex(int start, int father){
    viz[start] = 1;
    // vizitam nodul din care plecam
    up[start] = nivel[start];
    S[++top] = start;

    for(int i = 0; i < A[start].size(); i++){
        // parcurgem toti vecinii nodului start
        if(i != father ){
            //daca nu e nodul din care am venit
            if(viz[A[start][i]]){

                // daca am mai vizitat acest vecin
                up[start] = min(up[start], nivel[A[start][i]]);
            }
            else{
                //daca nu a mai fost vizitat
                nivel[A[start][i]] = nivel[start] +1;
                DFS_Biconex(A[start][i], start);

                if(up[A[start][i]] >= nivel[start]){
                    nrCompBiconexe++;

                    while(top && S[top] != A[start][i]){
                        compBiconexe[nrCompBiconexe].push_back(S[top--]);
                    }
                    
                    compBiconexe[nrCompBiconexe].push_back(S[top--]);
                    compBiconexe[nrCompBiconexe].push_back(start);
                }
                up[start] = min(up[start], up[A[start][i]]);
            }
        }
    }
}

void Graf :: AfisareBiconex()
{
    fout << nrCompBiconexe << "\n";
    for ( int i = 1; i <= nrCompBiconexe; i++ ){
        for ( int j = 0; j < compBiconexe[i].size(); j++ )
            fout << compBiconexe[i][j] << " ";
        fout << "\n";
    }
}


int main(){
    int N, M;
    fin >> N >> M;
    Graf G(N,M);
    G.CitireGOrientat();
    G.DFS_Biconex(1,0);
    G.AfisareBiconex();

    return 0;
}