Cod sursa(job #2819784)

Utilizator pizzandreeaCiurescu Andreea pizzandreea Data 19 decembrie 2021 00:48:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

#define MAX 100001

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



class Graf{
public:
    //date membre
    vector <int> A[MAX];    //liste de adiacenta

    int mM, mN;

    //constructor

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


    void BFS();

    void DFS(int start, bool viz[MAX]);
    void ComponenteConexe();


    void ComponenteBiconexe();
    void DFS_Biconex(int start, int father, vector <bool> &viz, vector <int> &up, vector <int> &nivel, stack <int> &S, int & nrComp, vector<vector<int>> &compBiconexe);
    void AfisareBiconex(int nrComp, vector<vector<int>> &compBiconexe);

};


void Graf :: BFS(){

    int x, y, start;
    fin >> start;
    for(int i = 1; i <= mM; i++){
        fin >> x >> y;
        A[x].push_back(y);
    }

    bool viz[MAX] = {false};
    queue <int> Q;

    int lg[MAX] = {0};  // lungimea drumului

    // vizitam nodul curent
    viz[start] = true;
    // il punem in coada
    Q.push(start);

    // fout<<1;
    while ( !Q.empty() ){
        x = Q.front();
        Q.pop();
        // preluam primul element din coada apoi il eliminam din coada

        for(int i = 0; i < A[x].size(); i++){
            // parcurgem toti vecinii lui x
            if(viz[A[x][i]] == 0){   // daca nu am mai vizitat vecinul asta{
                Q.push(A[x][i]);

                // il vizitam
                viz[A[x][i]] = 1;
                // creste lungimea drumului
                lg[A[x][i]] = lg[x] + 1;

            }
        }
    }

    for(int i = 1; i <= mN; i++)
        if(viz[i] != 0)
            fout << lg[i] << " ";
        else
            fout << -1 << " ";

}

void Graf::DFS(int start, bool viz[MAX]) {
    viz[start] = true;
    // 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], viz);
        }
    }
}


void Graf::ComponenteConexe() {
    int x, y;

    for(int i = 1; i <= mM; i++){
        fin >> x >> y;
        A[x].push_back(y);
        A[y].push_back(x);
    }

    bool viz[MAX] = {false};
    int nrComp = 0;

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

    fout << nrComp;

}

void Graf::DFS_Biconex(int start, int father, vector<bool> &viz, vector<int> &up, vector<int> &nivel, stack<int> &S,
                       int &nrComp, vector<vector<int>> &compBiconexe) {
    viz[start] = true;
    // vizitam nodul din care plecam
    up[start] = nivel[start];
    S.push(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, viz, up, nivel, S, nrComp,compBiconexe);

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

                nrComp++;
                while ( !S.empty() && S.top() != i ){
                    compBiconexe[nrComp].push_back(S.top());
                    S.pop();
                }
                compBiconexe[nrComp].push_back(S.top());
                S.pop();
                compBiconexe[nrComp].push_back(start);
            }
            up[start] = min(up[start], up[i]);
        }
    }
}

void Graf::AfisareBiconex(int nrComp, vector<vector<int>> &compBiconexe) {
    fout << nrComp << "\n";
    for ( int i = 1; i <= nrComp; i++ ){
        for ( auto j : compBiconexe[i] )
            fout << j << " ";
        fout << "\n";
    }
}

void Graf::ComponenteBiconexe() {
    int x, y;
    vector <vector<int>> compBiconexe(mN+1);
//    bool viz[MAX] = {false};
    vector <bool> viz(mN+1,0);
    int nrComp = 0;
//    int up[MAX] = {0};
    vector <int> up(mN+1, 0);
//    int nivel[MAX] = {0};
    vector <int> nivel(mN+1, 0);
//    int S[MAX] = {0};
    stack <int> S;

//    int top = 0;

    for(int i = 1; i <= mM; i++){
        fin >> x >> y;
        A[x].push_back(y);
        A[y].push_back(x);
    }

    DFS_Biconex(1,0, viz, up, nivel, S, nrComp, compBiconexe);
    AfisareBiconex(nrComp, compBiconexe);
}



int main(){
    int N, M, S;
    fin >> N >> M;
    // fout << 1;
    Graf G(N,M);
    G.ComponenteBiconexe();


    return 0;
}