Cod sursa(job #2792923)

Utilizator MihaiLazar26Lazar Mihai MihaiLazar26 Data 2 noiembrie 2021 14:56:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

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

#define NMAX 100001
#define MMAX 1000005

class Graf{
    vector<int> nod[NMAX];
    vector<int> viz;
    vector<int> nma;
    queue<int> coada;
    stack<int> stiva;
    vector<vector<int>> componente;
    int nrNoduri, nrMuchi;
    bool orientat = false, neorientat = false;

    void setOrientat(bool orientat = true){
        if(orientat) this->orientat = true, this->neorientat = false;
        else this->orientat = false, this->neorientat = true;
    }

    void setNeorientat(bool neorientat = true){
        if(neorientat) this->neorientat = true, this->orientat = false;
        else this->neorientat = false, this->orientat = true;
    }

    void setViz(int nod, int val){
        this->viz.assign(nod + 1, val);
    }

    void actBFS(int S);
    void actDFS(int S);
    void biconexeDFS(int S, int Tata);
public:

    void citire(int nrNoduri, int nrMuchi, vector<pair<int, int>> muchi, bool orientat = true){
        if(orientat) setOrientat();
        else setNeorientat();
        this->nrNoduri = nrNoduri;
        this->nrMuchi = nrMuchi;
        for(auto i : muchi){
            this->nod[i.first].push_back(i.second);
            if(this->neorientat) this->nod[i.second].push_back(i.first);

        }
    }


    vector<int> BFS(int S);

    int DFS();

    vector<vector<int>> compBiconexe();
};
Graf graf;


void Graf::actBFS(int S){
    this->coada.push(S);
    this->viz[S] = 0;
    while(!coada.empty()){
        int current = coada.front();
        coada.pop();
        int dist = viz[current] + 1;
        for(auto vecin : nod[current]){
            if(viz[vecin] == -1){
                viz[vecin] = dist;
                coada.push(vecin);
            }
        }
    }
}

vector<int> Graf::BFS(int S){
    setViz(this->nrNoduri, -1);
    actBFS(S);
    return this->viz;
}

void Graf::actDFS(int S){
    viz[S] = 1;
    for(auto vecini : nod[S]){
        if(!viz[vecini]) actDFS(vecini);
    }
}

int Graf::DFS(){
    int componente = 0;
    setViz(nrNoduri, 0);
    for(int i = 1; i <= nrNoduri; i++){
        if(!viz[i]) actDFS(i), ++componente;
    }
    return componente;
}

void Graf::biconexeDFS(int S, int Tata){
    nma[S] = viz[S] = viz[Tata] + 1;
    stiva.push(S);
    for(auto vecin : nod[S]){
        if(vecin != Tata){
            if(viz[vecin]){
                nma[S] = min(nma[S], viz[vecin]);
            }
            else{
                biconexeDFS(vecin, S);
                nma[S] = min(nma[S], nma[vecin]);

                if(viz[S] <= nma[vecin]){
                    vector<int> comp;
                    while(stiva.top() != vecin){
                        comp.push_back(stiva.top());
                        stiva.pop();
                    }
                    comp.push_back(vecin);
                    stiva.pop();
                    comp.push_back(S);
                    componente.push_back(comp);
                }
            }
        }
    }

}

vector<vector<int>> Graf::compBiconexe(){
    viz.assign(nrNoduri+1, 0);
    nma.assign(nrNoduri+1, 0);
    biconexeDFS(1,0);
    return componente;
}
void rezolvareBFS(){
    vector<pair<int, int>> muchi;
    int n, m, s;
    fin>>n>>m>>s;
    for(int i = 1; i <= m; i++){
        int x, y;
        fin>>x>>y;
        muchi.push_back(make_pair(x, y));
    }
    graf.citire(n, m, muchi);
    vector<int> sol = graf.BFS(s);
    for(int i = 1; i <= n; i++){
        fout<<sol[i]<<" ";
    }
}

void rezolvareDFS(){
    vector<pair<int, int>> muchi;
    int n, m;
    fin>>n>>m;
    for(int i = 1; i <= m; i++){
        int x, y;
        fin>>x>>y;
        muchi.push_back(make_pair(x, y));
    }
    graf.citire(n, m, muchi, false);

    int res = graf.DFS();
    fout<<res;
}

void rezolvareBiconexe(){
    vector<pair<int, int>> muchi;
    int n, m;
    fin>>n>>m;
    for(int i = 1; i <= m; i++){
        int x, y;
        fin>>x>>y;
        muchi.push_back(make_pair(x, y));
    }
    graf.citire(n, m, muchi, false);

    vector<vector<int>> sol = graf.compBiconexe();
    int nrComp = sol.size();
    fout<<nrComp<<'\n';
    for(int i = 0; i < nrComp; i++)
    {
        for(auto nod : sol[i])
            fout<<nod<<' ';
        fout<<'\n';
    }


}
int main(){
    rezolvareBiconexe();
}