TAXI – Omówienie zadania

Szczegółowe omówienie zadania TAXI:
Link do powyższego omówienia zadania TAXI:
https://youtu.be/-6XSy1IUlgg?t=956


Zadanie TAXI to zadanie grafowe i wymaga użycia techniki Preorder / Postorder.
Te wartości uzyskujemy stosując algorytm DFS.


Autor zadania: Kacper Omielańczyk

——–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

——-

Kod C++ programu TAXI, który jest omówiony w powyższym filmie i który otrzymuje 100%

#include <bits/stdc++.h>
using namespace std;

const int MAX_WIERZCHOLKOW = 5e5 + 7;
vector<int> krawedzie[MAX_WIERZCHOLKOW];
bool czy_odwiedzony_wierzcholek[MAX_WIERZCHOLKOW];
int preorder [MAX_WIERZCHOLKOW];
int postorder [MAX_WIERZCHOLKOW];

int act_preorder_postorder;

void DFS (int v) {
 int i;
 czy_odwiedzony_wierzcholek[v] = true;
 preorder [v] = act_preorder_postorder;
 ++act_preorder_postorder;
 for(i=0; i<krawedzie[v].size(); i++){
    if( czy_odwiedzony_wierzcholek[ krawedzie[v][i] ] == false ){
       DFS( krawedzie[v][i] );
    }
 }
 postorder [v] = act_preorder_postorder;
 ++act_preorder_postorder;
}

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 
 int liczba_skrzyzowan, liczba_pytan;
 int wierz_a, wierz_b, wierz_taksowkarz;
 int i, j;
 int v, kraw;

 cin >> liczba_skrzyzowan;
 for (i=1; i<liczba_skrzyzowan; ++i) {
    cin >> wierz_a >> wierz_b;
    krawedzie[wierz_a].push_back(wierz_b);
    krawedzie[wierz_b].push_back(wierz_a);
 }

 act_preorder_postorder = 1;
 DFS (1); 

 cin >> liczba_pytan;
 for (i=1; i<=liczba_pytan; ++i) {
    cin >> wierz_taksowkarz;
    cin >> wierz_a;
    cin >> wierz_b;
    if ( (preorder[wierz_taksowkarz]<=preorder[wierz_a]) && (postorder[wierz_taksowkarz]>=postorder[wierz_a]) && 
	     (preorder[wierz_taksowkarz]<=preorder[wierz_b]) && (postorder[wierz_taksowkarz]>=postorder[wierz_b]))
	   cout << "TAK" << "\n";
    else
	   cout << "NIE" << "\n";
 }

 return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Taxi  

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz