Szczegółowe omówienie zadania TAXI:
Link do powyższego omówienia zadania TAXI:
https://youtu.be/-6XSy1IUlgg?t=956
https://youtu.be/-6XSy1IUlgg?t=956
Link do treści zadania TAXI:
https://szkopul.edu.pl/problemset/problem/tax/site
–
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