#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
vector <vector<int>> listaAd, listaTr, rez;
vector <int> vizitat, vizitatTr;
stack <int> stiva;
bool compara(int a, int b)
{
    return (a > b);
}
class Graf
{
   private:
       int nrN, nrM; ///Numar noduri, numar muchii
       vector <vector<int>> listaAd; ///lista de adiacenta graf
   public:
       Graf(int, int, vector <vector<int>> &);
       Graf(const Graf &graf);
       ~Graf();
       int get_noduri();
       int get_muchii();
       vector <vector<int>> get_lista();
       void set_noduri(int);
       void set_muchii(int);
       void set_lista(vector<vector<int>>);
       void afisare(ostream&);
       friend ostream& operator<<(ostream& out, Graf &g); ///supraincarcare operator <<
       ///BFS
       void BFS(ostream&, int);
       ///DFS
       void DFS(ostream &);
       void DoDfs(int, vector <int> &);
       ///SortareTopologica
       void sortareTopologica(ostream&, int []);
       ///HavelHakimi
       int existaGrafHH(vector <int> &, int);
       ///ComponenteTareConexe
       void ctc(ostream &);
       void dfs1(int);
       void dfs2(int, vector <int> &);
       ///MuchiiCritice
       void DfsMuchiiCritice(int, int, vector <int> &, vector <int> &, vector <int> &, vector <vector<int>> &, ostream &);
};

Graf :: Graf(int nrNoduri, int nrMuchii, vector <vector<int>> &lista)
{
     nrN = nrNoduri;
     nrM = nrMuchii;
     listaAd = lista;
}

Graf :: Graf(const Graf & graf)
{
     nrN = graf.nrN;
     nrM = graf.nrM;
     listaAd = graf.listaAd;
}

Graf :: ~Graf()
{
    nrN = 0;
    nrM = 0;
    listaAd.clear();
}

int Graf :: get_noduri()
{
    return nrN;
}

int Graf :: get_muchii()
{
    return nrM;
}

vector <vector<int>> Graf :: get_lista()
{
    return listaAd;
}

void Graf :: set_noduri(int noduri)
{
    nrN = noduri;
}

void Graf :: set_muchii(int muchii)
{
    nrM = muchii;
}

void Graf :: set_lista(vector<vector<int>> lista)
{
    listaAd = lista;
}

void Graf :: afisare(ostream &out)
{
    out << "Numar de noduri: " << nrN << "\n";
    out << "Numar de muchii: " << nrM << "\n";
    for (int i = 0; i < nrN; i++)
        for (int j = 0; j < listaAd[i].size(); j++)
           {
               out << "Muchia "  << i << " " << listaAd[i][j];
               out << "\n";
           }
}

ostream& operator<<(ostream& out, Graf &g)
{
    g.afisare(out);
    return out;
}

///BFS
void Graf :: BFS(ostream &out, int start)
{
    int cost[nrN + 1], S;
    for (int i = 1; i <= nrN; i++)
        cost[i] = -1; ///initializam costurile cu -1
    queue <int> coada;
    coada.push(start); ///adaugam in coada nodul de start
    cost[start] = 0; ///costul pentru nodul de start este 0
    while (!coada.empty()) ///cat timp avem elemente in coada
    {
        S = coada.front();
        for (int i = 0; i < listaAd[S].size(); i++) ///parcurgem vecinii nodului curent
        {
            int nod_curent = listaAd[S][i];
            if (cost[nod_curent] == -1) ///daca e nevizitat
            {
                cost[nod_curent] = cost[S] + 1; ///actualizam costul
                coada.push(nod_curent); ///adaugam in coada vecinul
            }
        }
        coada.pop(); ///eliminam nodul curent din coada
    }
    for (int i = 1; i <= nrN; i++)
        out << cost[i] << " "; ///afisam costurile pentru fiecare nod
}

///DFS
void Graf :: DoDfs(int nod, vector <int> &viz)
{
    viz[nod] = 1; ///vizitam nodul curent
    for (int i = 0; i < listaAd[nod].size(); i++) ///parcurgem vecinii nodului curent
    {
        int nod_curent = listaAd[nod][i];
        if (viz[nod_curent] == 0) ///daca vecinul este nevizitat
            DoDfs(nod_curent, viz);
    }
}

void Graf :: DFS(ostream &out)
{
    vector <int> viz(nrN + 1, 0); ///initializam vectorul viz
    int nrCC = 0; ///numar componente conexe
    for (int i = 1; i <= nrN; i++)
    {
        if (viz[i] == 0) ///daca nodul este nevizitat
        {
            DoDfs(i, viz);
            nrCC ++;
        }
    }
    out << nrCC;
}

///SortareTopologica
void Graf :: sortareTopologica(ostream &out, int grade[])
{
    queue <int> coada;
    vector <int> rez;
    for (int i = 1; i <= nrN; i++)
        if (grade[i] == 0)
            coada.push(i); ///adaugam in coada nodurile cu gradul intern 0
    while (!coada.empty())
    {
        int nod_curent = coada.front();
        rez.push_back(nod_curent);
        coada.pop();
        for (int i = 0; i < listaAd[nod_curent].size(); i++) ///parcurgem vecinii
        {
            int vecin = listaAd[nod_curent][i];
            grade[vecin]--; ///scadem 1 tuturor gradelor nodurilor adiacente
            if (grade[vecin] == 0) ///daca gradul intern a devenit 0, il adaugam in coada
                coada.push(vecin);
        }
    }
    for (int i=0; i < rez.size(); i++)
        out << rez[i] << " ";
}

///HavelHakimi
int Graf :: existaGrafHH(vector <int> &v, int n)
{
    int ok = 1;
    while (ok == 1)
    {
        sort(v.begin(), v.end(), compara); ///sortam descrescator gradele nodurilor
        if (v[0] == 0) ///daca toate gradele sunt egale cu 0 - primul element 0 in ordine descrescatoare
            break; ///exista graf
        int nr = v[0]; ///extragem primul grad
        v.erase(v.begin() + 0);
        if (nr > v.size()) ///daca gradul este mai mare decat numarul de elemente ramase
         {
            ok = 0; ///nu exista graf
            break;
         }
        for (int i = 0; i < nr; i++) ///parcurgem urmatoarele nr elemente
        {
            v[i] = v[i] - 1; ///scadem 1 din grad
            if (v[i] < 0) ///daca gradul a devenit -1
                {
                    ok = 0; ///nu exista graf
                    break;
                }
        }
    }
    if (ok == 1) return 1;
    return 0;
}

///Ctc
void Graf :: dfs1(int nod)
{
    vizitat[nod] = 1;
    for (int i = 0; i < listaAd[nod].size(); i++)
    {
        int nod_curent = listaAd[nod][i];
        if (vizitat[nod_curent] == 0)
            dfs1(nod_curent);
    }
   stiva.push(nod); ///adaugam in stiva nodurile
}

void Graf :: dfs2(int nod, vector <int> &vector_aux)
{
    vector_aux.push_back(nod); ///adaugam nodul la componenta curenta
    vizitatTr[nod] = 1;
    for (int i = 0; i < listaTr[nod].size(); i++)
    {
        int nod_curent = listaTr[nod][i];
        if (vizitatTr[nod_curent] == 0)
            dfs2(nod_curent, vector_aux);
    }
}

void Graf :: ctc(ostream &out)
{
    int nr = 0;
    for (int i = 1; i <= nrN; i++)
        if (vizitat[i] == 0)
            dfs1(i); ///primul dfs
    while (stiva.empty() == 0) ///parcurgem stiva
    {
       int v = stiva.top();
       stiva.pop();
       if (vizitatTr[v] == 0) ///daca nodul curent din stiva e nevizitat
       {
          vector <int> vector_aux;
          dfs2(v, vector_aux); ///al doilea dfs
          rez.push_back(vector_aux); ///adaugam la solutie componenta curenta
          nr++; ///incrementam numarul de componente
       }
    }
   // out << "Numarul de componente tare conexe: " << nr << "\n";
    out << nr << "\n";
   // out << "Componentele: " << "\n";
    for (int i = 0; i < rez.size(); i++)
    {
       if (rez[i].size() != 0)
        {
           for (int j = 0; j < rez[i].size(); j++)
              out << rez[i][j] << " ";
           out << "\n";
        }
    }
}

///MuchiiCritice
void Graf :: DfsMuchiiCritice(int nod, int tata, vector <int> &vizitat, vector <int> &nivel, vector <int> &nivelInt, vector <vector<int>> &listaAd,
                              ostream &out)
{
    vizitat[nod] = 1;
    nivel[nod] = nivel[tata] + 1; ///actualizam nivelul
    nivelInt[nod] = nivel[nod]; ///actualizam nivelul de intoarcere
    for (int i = 0; i < listaAd[nod].size(); i++)
    {
        int copil = listaAd[nod][i];
        if (copil != tata)
        {
            if (vizitat[copil] == 1)
                {
                    if (nivelInt[nod] > nivel[copil]) ///actualizam nivelul de intoarcere acolo unde gasim o muchie de intoarcere
                       nivelInt[nod] = nivel[copil];
                }
            else
            {
                DfsMuchiiCritice(copil, nod, vizitat, nivel, nivelInt, listaAd, out);
                if (nivelInt[nod] > nivelInt[copil]) ///actualizam nivelul de intoarcere in cazul in care un copil are acest nivel mai mic
                    nivelInt[nod] = nivelInt[copil];
                if (nivel[nod] < nivelInt[copil]) ///conditie muchii critice
                    out << nod << " " << copil << "\n";
            }
        }
    }
}

///-------------------------BFS------------------------------
void problemaBFS()
{
    int n, s, st, dr, m;
    cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti nodul start: ";
    cin >> s;
    cout << "Introduceti muchiile: ";
    vector <vector<int>> listaAd(n + 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> st >> dr;
        listaAd[st].push_back(dr);
    }
    Graf g(n, m, listaAd);
    g.BFS(cout, s);
}

///-------------------------DFS--------------------------------
void problemaDFS()
{
    int n, m, st, dr;
    cout << "Numerotare noduri de la index 1! Graf neorientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti muchiile: ";
    vector <vector<int>> listaAd(n + 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> st >> dr;
        listaAd[st].push_back(dr);
        listaAd[dr].push_back(st);
    }
    Graf g(n, m, listaAd);
    g.DFS(cout);
}

///------------------Havel Hakimi-------------------------
void problemaHavelHakimi()
{
    vector <int> v;
    int n, el;
    cout << "Introduceti numarul de elemente: ";
    cin >> n;
    cout << "Introduceti gradele: ";
    for (int i = 0; i < n; i++)
    {
        cin >> el;
        v.push_back(el);
    }
    vector <vector<int>> vgol(n+1,{0});
    Graf g(0, 0, vgol);
    int rez = g.existaGrafHH(v, n);
    if (rez == 1)
        cout << "Da, exista graf!";
    else cout << "Nu, nu exista graf!";
}

///------------------Sortare Topologica------------------
void problemaSortareTopologica()
{
    int n, m, st, dr, grade[50001] = {0};
    cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti muchiile: ";
    vector <vector<int>> listaAd (n + 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> st >> dr;
        listaAd[st].push_back(dr);
        grade[dr]++;
    }
    Graf g(n, m, listaAd);
    g.sortareTopologica(cout, grade);
}

///---------------Componente Tare Conexe-------------------
void problemaComponenteTareConexe()
{
    int n, m, st, dr;
    /*cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti muchiile: ";*/
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin >> n >> m;
    rez = vector <vector<int>> (n + 1);
    listaTr = vector <vector<int>> (n + 1);
    listaAd = vector <vector<int>> (n + 1);
    vizitat = vector <int> (n + 1, 0);
    vizitatTr = vector <int> (n + 1, 0);
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr;
        listaAd[st].push_back(dr);
        listaTr[dr].push_back(st);
    }
    Graf g(n, m, listaAd);
    g.ctc(fout);
    fin.close();
    fout.close();
}

///------------------Muchii Critice---------------------
void problemaCriticalConnectionsLeetCode()
{
    int n, m, st, dr;
    cout << "Numerotare noduri de la index 0! Graf neorientat!" << "\n";
    cout << "Introduceti numarul de noduri: ";
    cin >> n;
    cout << "Introduceti numarul de muchii: ";
    cin >> m;
    cout << "Introduceti muchiile: ";
    vector <vector<int>> listaAd(n + 1);
    vector <int> vizitat(n + 1, 0);
    vector <int> nivel(n + 1, 0);
    vector <int>nivelInt(n + 1, 0);
    for (int i = 1; i <= m; i++)
    {
        cin >> st >> dr;
        listaAd[st].push_back(dr);
        listaAd[dr].push_back(st);
    }
    Graf g(n, m, listaAd);
    cout << "Muchii critice: ";
    g.DfsMuchiiCritice(0, 0, vizitat, nivel, nivelInt, listaAd, cout);
}

int main()
{
    /*cout << "---Sora Andreea-Ioana/grupa 234/Tema 1 - Algoritmi Fundamentali---" << "\n";
    cout << "Probleme: " << "\n";
    cout << "1. BFS - drumuri minime de la un nod start la toate celelalte" << "\n";
    cout << "2. DFS - Numarul de componente conexe" << "\n";
    cout << "3. Sortare Topologica" << "\n";
    cout << "4. Havel Hakimi" << "\n";
    cout << "5. Componente Tare Conexe" << "\n";
    cout << "6. Muchii Critice - LeetCode" << "\n";
    cout << "Introduceti numarul problemei pe care doriti sa o rulati: ";
    int numar;
    cin >> numar;
    cout << "\n";
    if (numar < 1 || numar >= 7)
        cout << "Numar invalid!";
    else if (numar == 1) problemaBFS();
          else if (numar == 2) problemaDFS();
                else if (numar == 3) problemaSortareTopologica();
                     else if (numar == 4) problemaHavelHakimi();
                                 ///HavelHakimi
                                 ///(2,2,2,2) -> (1,1,2) -> (2,1,1) -> (0,0)
                                 ///  nod ------- nod
                                 ///   |           |
                                 ///   |           |
                                 ///  nod-------- nod
                                 /// (3,2,1,1,0) -> (1,0,0,0) -> (-1,0,0)
                             else if (numar == 5) problemaComponenteTareConexe();
                                     else if (numar == 6) problemaCriticalConnectionsLeetCode();*/
     problemaComponenteTareConexe();
     return 0;
}