Advertisement
Guest User

Untitled

a guest
May 27th, 2017
133
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void dfs(vector <vector<int> > lista_sasiedztwa)
  2. {
  3.     vector <char> kolory(lista_sasiedztwa.size(), 'B'); // VS
  4.     vector <int> tablica_numerow_wierzcholkow(lista_sasiedztwa.size(), 0); // VN
  5.     vector <int> tablica_parametrow(lista_sasiedztwa.size(), 0); //VLow
  6.     vector <bool> czy_jest_na_stose(lista_sasiedztwa.size(), false);
  7.     stack <int> odwiedzone_wierzcholki;
  8.     vector <lista*> lista_spojnych(lista_sasiedztwa.size());
  9.  
  10.     int cvn;
  11.  
  12.        dfs_visit(lista_sasiedztwa, kolory, odwiedzone_wierzcholki, 0, tablica_numerow_wierzcholkow, tablica_parametrow, czy_jest_na_stose, cvn, lista_spojnych);
  13.        odczytaj_wyniki(lista_spojnych);
  14. }
  15. void dfs_visit(vector <vector<int> > &lista_sasiedztwa, vector <char> &kolory, stack <int> &odwiedzone_wierzcholki,
  16.                 int wierzcholek, vector <int> &tablica_numerow_wierzcholkow, vector <int> &tablica_parametrow, vector <bool> &czy_jest_na_stose, int &cvn, vector <lista*> &lista_spojnych)
  17. {
  18.     cvn += 1;
  19.     tablica_numerow_wierzcholkow[wierzcholek] = cvn;
  20.     tablica_parametrow[wierzcholek] = cvn;
  21.     odwiedzone_wierzcholki.push(wierzcholek);
  22.     kolory[wierzcholek] = 'S';
  23.     czy_jest_na_stose[wierzcholek] = true;
  24.  
  25.     for(int i = 0; i < lista_sasiedztwa[wierzcholek].size(); i++)
  26.     {
  27.         if(kolory[lista_sasiedztwa[wierzcholek][i]] == 'B')
  28.         {
  29.             dfs_visit(lista_sasiedztwa,  kolory, odwiedzone_wierzcholki, lista_sasiedztwa[wierzcholek][i], tablica_numerow_wierzcholkow, tablica_parametrow,
  30.                        czy_jest_na_stose, cvn, lista_spojnych);
  31.  
  32.             tablica_parametrow[wierzcholek] = min(tablica_parametrow[wierzcholek], tablica_parametrow[lista_sasiedztwa[wierzcholek][i]]);
  33.         }
  34.         else if(czy_jest_na_stose[lista_sasiedztwa[wierzcholek][i]] == false)
  35.         {
  36.             tablica_parametrow[wierzcholek] =
  37.             min(tablica_parametrow[wierzcholek], tablica_numerow_wierzcholkow[lista_sasiedztwa[wierzcholek][i]]);
  38.         }
  39.     }
  40.     lista *roboczy;
  41.  
  42.     if(tablica_parametrow[wierzcholek] != tablica_numerow_wierzcholkow[wierzcholek])
  43.     {
  44.         lista_spojnych[wierzcholek] = NULL;
  45.  
  46.         do
  47.         {
  48.                 roboczy = new lista;
  49.                 roboczy->wartosc = odwiedzone_wierzcholki.top();
  50.                 roboczy->nastepny = NULL;
  51.                 odwiedzone_wierzcholki.pop();
  52.                 czy_jest_na_stose[roboczy->wartosc] = false;
  53.                 lista_spojnych[wierzcholek] = roboczy;
  54.  
  55.         }while(roboczy->wartosc != wierzcholek);
  56.     }
  57. }
  58. void odczytaj_wyniki(vector <lista*> lista_spojnych)
  59. {
  60.     cout<<lista_spojnych.size()<<endl;
  61.     cout<<*(lista_spojnych[0]).wartosc;
  62. }
Advertisement
RAW Paste Data Copied
Advertisement