/*
9 13
0 1
0 4
1 2
2 5
4 1
4 3
4 5
4 6
4 7
5 8
7 6
8 4
8 7
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
#include <stack>
using namespace std;

struct lista
{
  int wartosc;
  lista *nastepny;
};
int licznikI = 0;

void wczytaj_z_pliku();
void zmien_rozmiar(vector <vector<int> > &lista_sasiedztwa, vector <int> wiersz, int ilosc_wierzcholkow);
void dodaj_do_listy(vector <vector<int> > &lista_sasiedztwa, int pierwszy_wierzcholek, int drugi_wierzcholek);
void przeczytaj_sasiadow(vector <vector<int> > lista_sasiedztwa);
void dfs(vector <vector<int> > &lista_sasiedztwa);
void dfs_visit(vector <vector<int> > &lista_sasiedztwa, stack <int> &odwiedzone_wierzcholki,
                int wierzcholek, vector <int> &tablica_numerow_wierzcholkow, vector <int> &tablica_parametrow, vector <bool> &czy_jest_na_stose, int &cvn, vector <lista*> &lista_spojnych);
void odczytaj_skladowe(vector <lista*> lista_spojnych);
void sprzatnij(vector <lista*> &lista_spojnych);

int main()
{
    wczytaj_z_pliku();

    return 0;
}

void wczytaj_z_pliku()
{
    string linia;
    string bufor;

    int ilosc_wierzchlkow;
    int rozmiar_lini;
    int id = 0;
    int ilosc_krawedzi;
    int pierwszy_wierzcholek;
    int drugi_wierzcholek;


    vector <int> wiersz;
    vector <vector<int> > lista_sasiedztwa(1, wiersz);

    fstream plik;
    plik.open("plik.txt",ios::in);

    while(!plik.eof())
    {
        getline(plik,linia);
        rozmiar_lini = linia.size()-1;
        switch(id)
        {
// wczytuje liczbe z napisu do spacji i po spacji i odpowiednio rozdzielam wiedzac jakie jest ulozenie liczb w pliku
// np   string = '1245 567'; liczba a = 1245, liczba b = 567
        case 0:
        {
            for(int i=0; i < rozmiar_lini; i++)
            {
                if(linia[i] == ' ')
                {
                    bufor.clear();
                    for(int j=0; j < i; j++)
                    {
                        bufor[j] = linia[j];
                    }

                    ilosc_wierzchlkow = atoi(bufor.c_str());
                    bufor.clear();

                    zmien_rozmiar(lista_sasiedztwa, wiersz, ilosc_wierzchlkow);

                    int roboczy = 0;

                    for(int j = i+1; j < rozmiar_lini; j++)
                    {
                        bufor[roboczy] = linia[j];
                        roboczy++;
                    }
                    ilosc_krawedzi = atoi(bufor.c_str());
                }
            }
        }
        break;

        default:
        {
            for(int i=0; i < rozmiar_lini; i++)
            {
                if(linia[i] == ' ')
                {
                    bufor.clear();
                    for(int j=0; j < i; j++)
                    {
                        bufor[j] = linia[j];
                    }
                    pierwszy_wierzcholek = atoi(bufor.c_str());

                    int roboczy = 0;
                    for(int j = i + 1; j <= rozmiar_lini; j++)
                    {
                        bufor[roboczy] = linia[j];
                        roboczy ++;
                    }
                    roboczy = 0;
                    drugi_wierzcholek = atoi(bufor.c_str());
                    bufor.clear();

                    dodaj_do_listy(lista_sasiedztwa, pierwszy_wierzcholek, drugi_wierzcholek);
                }
            }
        }
        break;
        }//koniec switch
        id++;
    } //koniec while
plik.close();
//przeczytaj_sasiadow(lista_sasiedztwa);
dfs(lista_sasiedztwa);
}// koniec funkcji

void zmien_rozmiar(vector <vector<int> > &lista_sasiedztwa, vector <int> wiersz, int ilosc_wierzcholkow)
{
    lista_sasiedztwa.resize(ilosc_wierzcholkow, wiersz);
}
void dodaj_do_listy(vector <vector<int> > &lista_sasiedztwa,int pierwszy_wierzcholek, int drugi_wierzcholek)
{
    lista_sasiedztwa[pierwszy_wierzcholek].push_back(drugi_wierzcholek);
}
void przeczytaj_sasiadow(vector <vector<int> > lista_sasiedztwa)
{

    for(int i = 0; i < lista_sasiedztwa.size(); i++)
    {
        for(int j = 0; j < lista_sasiedztwa[i].size(); j++)
        {
            cout<<lista_sasiedztwa[i][j]<<endl;
        }
        cout<<endl;
    }
}
void dfs(vector <vector<int> > &lista_sasiedztwa)
{
    vector <int> tablica_numerow_wierzcholkow(lista_sasiedztwa.size(), 0); // VN
    vector <int> tablica_parametrow(lista_sasiedztwa.size(), 0); //VLow
    vector <bool> czy_jest_na_stose(lista_sasiedztwa.size(), false);
    stack <int> odwiedzone_wierzcholki;
    vector <lista*> lista_spojnych(lista_sasiedztwa.size(), NULL);


    int cvn = 0;

       for(int i = 0; i < lista_sasiedztwa.size(); i++)
       {
           if(!tablica_numerow_wierzcholkow[i])
           {
              dfs_visit(lista_sasiedztwa, odwiedzone_wierzcholki, i, tablica_numerow_wierzcholkow, tablica_parametrow, czy_jest_na_stose, cvn, lista_spojnych);
           }
       }

       odczytaj_skladowe(lista_spojnych);
       //sprzatnij(lista_spojnych);
}
void dfs_visit(vector <vector<int> > &lista_sasiedztwa, stack <int> &odwiedzone_wierzcholki,
                int wierzcholek, vector <int> &tablica_numerow_wierzcholkow, vector <int> &tablica_parametrow, vector <bool> &czy_jest_na_stose, int &cvn, vector <lista*> &lista_spojnych)
{

    tablica_numerow_wierzcholkow[wierzcholek] = tablica_parametrow[wierzcholek] = cvn;
    cvn++;
    odwiedzone_wierzcholki.push(wierzcholek);
    czy_jest_na_stose[wierzcholek] = true;

    for(int i = 0; i < lista_sasiedztwa[wierzcholek].size(); i++)
    {
            if(!tablica_numerow_wierzcholkow[lista_sasiedztwa[wierzcholek][i]])
            {
                dfs_visit(lista_sasiedztwa, odwiedzone_wierzcholki, lista_sasiedztwa[wierzcholek][i], tablica_numerow_wierzcholkow, tablica_parametrow,
                       czy_jest_na_stose, cvn, lista_spojnych);

                tablica_parametrow[wierzcholek] = min(tablica_parametrow[wierzcholek], tablica_parametrow[lista_sasiedztwa[wierzcholek][i]]);
            }

            else if(czy_jest_na_stose[lista_sasiedztwa[wierzcholek][i]])
            {
                tablica_parametrow[wierzcholek] =
                min(tablica_parametrow[wierzcholek], tablica_numerow_wierzcholkow[lista_sasiedztwa[wierzcholek][i]]);

            }
    }

    if(tablica_parametrow[wierzcholek] == tablica_numerow_wierzcholkow[wierzcholek])
    {
        lista *roboczy;
        lista *start = NULL;
        int u;
        do
        {
            u = odwiedzone_wierzcholki.top();
            odwiedzone_wierzcholki.pop();
            czy_jest_na_stose[u] = false;

            roboczy = new lista;

            roboczy->wartosc = u;
            roboczy->nastepny = start;
            start = roboczy;

        }while(u != wierzcholek);
        lista_spojnych[licznikI] = start;
        licznikI++;
        delete roboczy;
        delete start;
    }
}
void odczytaj_skladowe(vector <lista*> lista_spojnych)
{
    for(int i = 0; i < lista_spojnych.size(); i++)
    {
        cout<<"SSS numer: "<<i<<endl;
        while(lista_spojnych[i] != NULL)
        {
            cout<<lista_spojnych[i]->wartosc<<"\t";
            lista_spojnych[i] = lista_spojnych[i]->nastepny;
        }
        cout<<endl;
    }
}
void sprzatnij(vector <lista*> &lista_spojnych)
{
    for(int i = 0; i < lista_spojnych.size(); i++)
    {
        lista_spojnych[i] = lista_spojnych[i]->nastepny;
        while(lista_spojnych[i] != NULL)
        {
            lista *roboczy;
            roboczy = lista_spojnych[i];
            lista_spojnych[i] = roboczy->nastepny;
            delete roboczy;
        }
    }
}
/*
Skladowe:


*/