#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <stack>
#include <algorithm>

using namespace std;

class Graf{
private:
    int m_nrNoduri;
    vector<vector<int>> m_listAdiacenta;
    vector<int> viz;
    vector<int> arrivalTimes;
    vector<int> lowLinkValues;
    vector<int> precedenti;
    vector<unordered_set<int>> componenteBiconexe;
    vector<vector<int>> ComponenteTareConexe;
    vector<vector<int>> vectorMuchiiiCritice;
public:
    void citireGrafNeorientat(char *fisier);
    void citireGrafOrientat(char *fisier);

    void BFS(int nod);
    void DFS(int nod);
    void tarjan(int nod, int& arrivalTimeCurent, stack<int>& StivaComponentaTareConexaCurenta, vector<int>& isInStiva);
    void sortareTopologica();
    bool hakimi(vector<int> valori, int nr_elemente);

    void initViz();
    void initArrivalTimes();
    void initLowLinkValues();
    void initPrecedenti();

    void afisDrumuriMinime(vector<int> drumurileMinime);
    void afisNumarComponenteConexe(char* fisier);
    void afisComponenteBiconexe(char* fisier);
    void afisComponenteTareConexe(char* fisier);
    void generateFromSecventa(char* fisierCitire, char* fisierIesire);
    void afisMuchiiCritice(char* fisier);

    void numaraComponenteTareConexe(char* fisier);
    int numaraComponenteConexe();
    vector<vector<int>> findMuchiiCritice();

    int citireBFSINfoarena();

    void DFSBiconexe(int nod, int prec, int pas, vector<pair<int,int>>& stivaComponentaBiconexaCurenta);
    void DFSSortareTopologica(int nod, stack<int>& sortare);
    void DFSCritice(int nod, int& pas);
};

void Graf::citireGrafNeorientat(char *fisier){
    ifstream f(fisier);
    vector<int> aux;
    int nrMuchii;

    f>>this->m_nrNoduri;
    this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);

    f>>nrMuchii;

    for(int i=0; i<nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->m_listAdiacenta[x].push_back(y);
        this->m_listAdiacenta[y].push_back(x);
    }
}


void Graf::citireGrafOrientat(char *fisier){
    ifstream f(fisier);
    vector<int> aux;
    int nrMuchii;

    f>>this->m_nrNoduri;
    this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);

    f>>nrMuchii;

    for(int i=0; i<nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->m_listAdiacenta[x].push_back(y);
    }
}

int Graf::citireBFSINfoarena(){
    ifstream f("bfs.in");

    vector<int> aux;
    int nrMuchii, nodSursa;

    f>>this->m_nrNoduri;
    this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);

    f>>nrMuchii;

    f>>nodSursa;

    for(int i=0; i<nrMuchii; i++){
        int x,y;
        f>>x>>y;
        this->m_listAdiacenta[x].push_back(y);
    }
    return nodSursa;
}

void Graf::initViz(){
    viz.assign(this->m_nrNoduri+1, 0);
}

void Graf::initArrivalTimes(){
    arrivalTimes.assign(this->m_nrNoduri+1, -1);
}

void Graf::initLowLinkValues(){
    lowLinkValues.resize(this->m_nrNoduri+1);
}

void Graf::initPrecedenti(){
    precedenti.resize(this->m_nrNoduri+1);
}

void Graf::BFS(int nod){
        //initializam vectorul de distante minime
    vector<int> distante;
    distante.assign(100001, 0);
    int curent;
        //in coada vom pune nodurile pe massura ce le parcurgem
    queue<int> coada;
        //initial toate nodurile sunt nevizitate, asaa ca initializam viz[orice nod] = 0
    this->initViz();
        //adaugam nodul sursa in coada si il marcam ca si vizitat
    coada.push(nod);
    viz[nod] = 1;
        //actualizam vectorul de distante pentru nodul curent cu distanta pana la el, adica 1
    distante[nod] = distante[nod] + 1;

        //facem BFS-ul
    while(!coada.empty()){
        curent = coada.front();
            //parcurgem vecinii nodului curent si pe fiecare vecin nevizitat il adaugam in coada, ii actualizam distanta pana la el si il marcam ca si vizitat
        for(int i=0; i < this->m_listAdiacenta[curent].size(); i++){
            if(viz[this->m_listAdiacenta[curent][i]] == 0){
                coada.push(this->m_listAdiacenta[curent][i]);
                distante[coada.back()] = distante[curent]+1;
                viz[this->m_listAdiacenta[curent][i]] = 1;
            }
        }
            //am terminat cu nodul curent, il scoatem din coada
        coada.pop();
    }

    this->afisDrumuriMinime(distante);
}

void Graf::afisDrumuriMinime(vector<int> drumuriMinime){
    ofstream g("bfs.out");
    for(int i=1; i <= this->m_nrNoduri; i++){
        g<<drumuriMinime[i] - 1<<" ";
    }
}


void Graf::DFS(int nod){
        //marcam nodul curent ca vizitat
    this->viz[nod] = 1;
        //parcurgem vecinii si pentru fiecare vecin nevizitat aplicam recursiv DFS
    for(int i=0; i<this->m_listAdiacenta[nod].size(); i++){
        if(this->viz[this->m_listAdiacenta[nod][i]] == 0){
            DFS(this->m_listAdiacenta[nod][i]);
        }
    }
}

int Graf::numaraComponenteConexe(){
        //numarul componentelor conexe il vom tine in nr
    int nr = 0;
        //initial toate nodurile sunt nevizitate
    this->initViz();

        //pentru fiecare nod nevizitat parcurgem din copil in copil prin DFS; de fiecare data cand dam de un nod nevizitat inseamna ca avem o noua componenta conexa
    for(int nod = 1; nod <= this->m_nrNoduri; nod++){
        if(this->viz[nod] == 0){
            nr++;
            DFS(nod);
        }
    }

    return nr;
}

void Graf::afisNumarComponenteConexe(char *fisier){
    ofstream g(fisier);

    g<<this->numaraComponenteConexe();
}

void Graf::DFSBiconexe(int nodCurent, int precedent, int pas, vector<pair<int,int>>& stivaComponentaBiconexaCurenta){
        //marcam ca vizitat nodul curent
        arrivalTimes[nodCurent] = pas;

        //momentan nivelul minim de intoarcere e nivelul curent, adica pasul
        lowLinkValues[nodCurent] = pas;

        //parcurgem vecinii nodului curent
        for(int i=0; i<this->m_listAdiacenta[nodCurent].size(); i++){
            int vecinCurent = this->m_listAdiacenta[nodCurent][i];
            if(vecinCurent != precedent){
                //verificam pe ce fel de muchie suntem
                //daca vecinul curent a mai fost vizitat inseamna ca am dat de o muchie de intoarcere, altfel suntem pe o muchie in jos
                if(arrivalTimes[vecinCurent] == -1){
                    //am dat de o noua muchie din componenta biconexa curenta, asa ca o adaugam in stiva
                    stivaComponentaBiconexaCurenta.push_back(make_pair(nodCurent,vecinCurent));
                    //apelam DFS pentru vecinul curent
                    DFSBiconexe(vecinCurent, nodCurent, pas + 1, stivaComponentaBiconexaCurenta);
                    //verificam daca atunci cand ne am dus mai departe in graf
                    // am dat de o muchie de intoarcere care ne duce mai sus decat ne ducea nodul acesta inainte
                    if(lowLinkValues[nodCurent] > lowLinkValues[vecinCurent]){
                        lowLinkValues[nodCurent] = lowLinkValues[vecinCurent];
                    }
                    //verificam daca am ajuns la finalul componentei biconexe
                    if(lowLinkValues[vecinCurent] >= arrivalTimes[nodCurent]){
                        //trebuie sa adaugam noua componenta biconexa in vectorul de componenete biconexe
                        //si sa golim stiva cu muchiile componentei biconexe curente
                        unordered_set<int> aux;
                        int aux1, aux2;
                        do{
                            aux1 = stivaComponentaBiconexaCurenta.back().first;
                            aux1 = stivaComponentaBiconexaCurenta.back().second;
                            stivaComponentaBiconexaCurenta.pop_back();
                            aux.insert(aux1);
                            aux.insert(aux2);
                        } while (aux1 != nodCurent || aux2 != vecinCurent);
                        componenteBiconexe.push_back(aux);
                    }
                }else{
                    //avem o muchie de intoarcere, trebuie sa verificam daca nu cumva duce mai sus
                    if(lowLinkValues[nodCurent] > arrivalTimes[vecinCurent]){
                        lowLinkValues[nodCurent] = arrivalTimes[vecinCurent];
                    }
                }
            }
        }
}

void Graf::afisComponenteBiconexe(char* fisier){
    vector<pair<int,int>> stivaComponentaBiconexaCurenta;
    ofstream g(fisier);
            //initial toate nodurile sunt nevizitate
    this->initArrivalTimes();
    this->initLowLinkValues();

    DFSBiconexe(1,0,0,stivaComponentaBiconexaCurenta);

    g<<componenteBiconexe.size()<<"\n";
    for(int i=0; i<componenteBiconexe.size(); i++){
        for(unordered_set<int>::iterator it = componenteBiconexe[i].begin(); it != componenteBiconexe[i].end(); it++){
            g<<*it<<" ";
        }
        g<<"\n";
    }
}


void Graf::numaraComponenteTareConexe(char* fisier){
    int arrivalTimeCurent = 0;
    stack<int> StivaComponentaTareConexaCurenta;
    vector<int> isInStiva;

    isInStiva.assign(this->m_nrNoduri + 1, 0);

    initArrivalTimes();
    initLowLinkValues();

    for(int i=1; i<=this->m_nrNoduri; i++){
        if(arrivalTimes[i] == -1){
            tarjan(i,arrivalTimeCurent,StivaComponentaTareConexaCurenta,isInStiva);
        }
    }
    afisComponenteTareConexe(fisier);
}

void Graf::tarjan(int nod, int& arrivalTimeCurent, stack<int>& StivaComponentaTareConexaCurenta, vector<int>& isInStiva){
    //adaugam nodul in componenta tare conexa curenta, adica in StivaComponentaTareConexaCurenta
    StivaComponentaTareConexaCurenta.push(nod);
    //marcam nodul ca facand parte din componenta tare conexa curenta prin vectorul isInStiva
    isInStiva[nod] = 1;
    //marcam nodul ca vizitat, atribuindu-i chiar timpul de ajungere
    arrivalTimes[nod] = arrivalTimeCurent;
    //valoarea low Link momentan este tot nivelul nodului curent
    lowLinkValues[nod] = arrivalTimeCurent;
    //marim timpul de ajungere pentru urmatorul pas
    arrivalTimeCurent++;
    //parcurgem vecinii nodului curent, facand un DFS
    for(int i=0; i<this->m_listAdiacenta[nod].size(); i++){
        int vecinCurent = this->m_listAdiacenta[nod][i];
        //verificam daca vecinul curent nu a fost inca vizitat
        if(arrivalTimes[vecinCurent] == -1){
            //aplicam tarjan pe nodul curent
            tarjan(vecinCurent, arrivalTimeCurent, StivaComponentaTareConexaCurenta, isInStiva);
            //la iesire incercam sa minimizam valoarea low link a nodului curent, daca vecinul la care suntem a facut in timpul tarjan-ului una mai mica
            if(lowLinkValues[vecinCurent] < lowLinkValues[nod]){
                lowLinkValues[nod] = lowLinkValues[vecinCurent];
            }
        }else{  //daca vecinul a fost deja vizitat
            //verificam daca vizitarea s-a produs in cadrul componentei tare conexe curente
            if(isInStiva[vecinCurent] == 1){
                //incercam sa minimizam valoarea low link a nodului curent, in cazul in care vecinul curent ajunge la un nod mai indepartat decat valoarea noastra curenta
                if(lowLinkValues[vecinCurent] < lowLinkValues[nod]){
                    lowLinkValues[nod] = lowLinkValues[vecinCurent];
                }
            }
        }
    }
    //verificam daca nodul curent inchide o componenta tare conexa
    if(arrivalTimes[nod] == lowLinkValues[nod]){
        //trebuie sa mutam componenta tare conexa curenta din stiva in vectorul cu toate componentele tare conexe din graf
        vector<int> aux;
        int nodAux;
        do{
            nodAux = StivaComponentaTareConexaCurenta.top();
            aux.push_back(nodAux);
            StivaComponentaTareConexaCurenta.pop();
            isInStiva[nodAux] = 0;
        }while(nodAux != nod);
        ComponenteTareConexe.push_back(aux);
    }
}

void Graf::afisComponenteTareConexe(char* fisier){
    ofstream g(fisier);

    g<<ComponenteTareConexe.size()<<"\n";
    for(int i=0; i<ComponenteTareConexe.size(); i++){
        for(int j=0; j<ComponenteTareConexe[i].size(); j++){
            g<<ComponenteTareConexe[i][j]<<" ";
        }
        g<<"\n";
    }
}


void Graf::DFSSortareTopologica(int nod, stack<int>& sortare){
    this->viz[nod] = 1;
    for(int i=0; i<this->m_listAdiacenta[nod].size();i++){
            int vecinCurent = this->m_listAdiacenta[nod][i];
        if(this->viz[vecinCurent] == 0){
            DFSSortareTopologica(vecinCurent, sortare);
        }
    }
    sortare.push(nod);
}

void Graf::sortareTopologica(){
    ofstream g("sortaret.out");
    this->initViz();
    stack<int> sortare;

    for(int i=1; i<=this->m_nrNoduri; i++){
        if(this->viz[i] == 0){
            DFSSortareTopologica(i, sortare);
        }
    }

    while(sortare.size() != 0){
        g<<sortare.top()<<" ";
        sortare.pop();
    }
}

bool Graf::hakimi(vector<int> valori, int nr_elemente){
    int suma = 0;

    sort(valori.begin()+1, valori.end(), greater<int>());

    while(valori[0] > 0){
        int gradCurent = valori[0];
        suma = suma + gradCurent;
        if(gradCurent > nr_elemente - 1){
            return false;
        }

        valori.erase(valori.begin() + 0);

        for(int i=1; i<=gradCurent; i++){
            valori[i]--;
            if(valori[i]<0){
                return false;
            }
        }
    }

   if(valori[0] == 0 && suma % 2 == 0) return true;

   return false;
}

void Graf::generateFromSecventa(char* fisierCitire, char* fisierIesire){
    ifstream f(fisierCitire);
    ofstream g(fisierIesire);

    vector<int> valori;
    int nr_valori;

    f>>nr_valori;
    valori.resize(nr_valori+1);

    for(int i=1; i<=nr_valori; i++){
        int grad;
        f>>grad;
        valori[i] = grad;
    }

    if(this->hakimi(valori,nr_valori)) g<<"DA";
    else g<<"NU";
}

void Graf::afisMuchiiCritice(char* fisier){
    ofstream g(fisier);

    vector<vector<int>> muchiileCritice;

    muchiileCritice = this->findMuchiiCritice();

    g<<"Numar muchii critice: "<<muchiileCritice.size()<<"\n";

    for(int i=0; i<muchiileCritice.size(); i++){
        for(int j=0; j<muchiileCritice[i].size(); j++){
            g<<muchiileCritice[i][j]<<" ";
        }
        g<<"\n";
    }
}

vector<vector<int>> Graf::findMuchiiCritice(){
    int arrivalTimeCurent = 0;

    initViz();
    initPrecedenti();
    initLowLinkValues();
    initArrivalTimes();

    for(int i=1; i<=m_nrNoduri; i++){
        if(viz[i] == 0){
            DFSCritice(i, arrivalTimeCurent);
        }
    }

    return this->vectorMuchiiiCritice;
}

void Graf::DFSCritice(int nodCurent, int& pas){
        //marcam nodul ca vizitat in vectorul viz, actualizam timpul lui de ajungere iar low link value momentan e fix timpul de ajungere
    viz[nodCurent] = 1;
    arrivalTimes[nodCurent] = pas;
    lowLinkValues[nodCurent] = pas;
        //crestem timpul de ajungere pentru urmatorul DFS
    pas++;
        //parcurgem vecinii nodului
    for(int i=0; i<m_listAdiacenta[nodCurent].size(); i++){
        int vecinCurent = m_listAdiacenta[nodCurent][i];
            //pentru fiecare vecin nevizitat, ii actualizam precedentul ca fiind nodul ai carui vecini ii parcurgem si intram in parcurgerea vecinilor vecinului
        if (viz[vecinCurent] == 0){
            precedenti[vecinCurent] = nodCurent;
            DFSCritice(vecinCurent, pas);
                //la iesirea din DFS incercam sa minimizam low link value pentru nodul curent, in cazul in care vecinul poate ajunge la un nod mai indepartat
            if(lowLinkValues[nodCurent] > lowLinkValues[vecinCurent]){
                lowLinkValues[nodCurent] = lowLinkValues[vecinCurent];
            }
                //in cazul in care este o muchie critica, o adaugam in vectorul de muchii critice
            if (lowLinkValues[vecinCurent] > arrivalTimes[nodCurent]){
                vectorMuchiiiCritice.push_back({nodCurent,vecinCurent});
            }
        }
        else{
                //pentru fiecare vecin deja vizitat incercam sa minimzam low link value pentru nodul nostru
            if (vecinCurent != precedenti[nodCurent]){
                if(lowLinkValues[nodCurent] > arrivalTimes[vecinCurent]){
                    lowLinkValues[nodCurent] = arrivalTimes[vecinCurent];
                }
            }
        }
    }
}

int main()
{
            /*BFS INFOARENA*/
    /*int nodPornire;
    Graf g;

    nodPornire = g.citireBFSINfoarena();

    g.BFS(nodPornire);*/

            /*DFS INFOARENA*/

    /*Graf g;

    g.citireGrafNeorientat("dfs.in");

    g.afisNumarComponenteConexe("dfs.out");*/

            /*COMPONENTE BICONEXE INFOARENA*/

    Graf g;

    g.citireGrafNeorientat("biconexe.in");

    g.afisComponenteBiconexe("biconexe.out");

            /*COMPONENTE TARE CONEXE INFOARENA*/

    /*Graf g;

    g.citireGrafOrientat("ctc.in");

    g.numaraComponenteTareConexe("ctc.out");*/

            /*SORTARE TOPOLOGICA INFOARENA*/

    /*Graf g;

    g.citireGrafOrientat("sortaret.in");

    g.sortareTopologica();*/

            /*HAVEL HAKIMI*/
    /*Graf g;
    g.generateFromSecventa("hakimi.in","hakimi.out");*/

            /*MUCHII CRITICE GRAF NEORIENTAT LEETCODE*/
    /*Graf g;

    g.citireGrafNeorientat("critice.in");

    g.afisMuchiiCritice("critice.out");*/
    return 0;
}