Cod sursa(job #2798536)

Utilizator pizzandreeaCiurescu Andreea pizzandreea Data 11 noiembrie 2021 15:16:17
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.25 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; // adaugam startul in stiva
 
    for ( auto i : A[start] ){
        // parcurgem toti vecinii nodului start

        if ( i == father ) continue;
        
        //daca nu e nodul din care am venit
        if ( viz[i] ){
            // daca am mai vizitat acest vecin
            up[start] = min(up[start], nivel[i]);
        }
        else{

            nivel[i] = nivel[start] + 1;
            DFS_Biconex(i, start);

            if ( up[i] >= nivel[start] ){

                nrCompBiconexe++;
                while ( top && S[top] != i ){
                    compBiconexe[nrCompBiconexe].push_back(S[top--]);
                }
                compBiconexe[nrCompBiconexe].push_back(S[top--]);
                compBiconexe[nrCompBiconexe].push_back(start);
            }
            up[start] = min(up[start], up[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;
}