Decorate Apple Tree – Omówienie zadania (Codeforces)

Szczegółowe omówienie zadania Decorate Apple Tree:

Link do powyższego omówienia zadania Decorate Apple Tree:
https://youtu.be/OA8BeVFvaNU?t=2907

Link do treści zadania Decorate Apple Tree:
https://codeforces.com/contest/1056/problem/D
Link do wszystkich zadań z tego contestu:
https://codeforces.com/contest/1056

——
Zadanie Decorate Apple Tree pokazuje
  • co to jest drzewo?
  • jak chodzić po grafie (drzewie) – używa w tym celu algorytmu DFS?
——
—–
Zadanie Decorate Apple Tree pochodzi z najpopularniejszej platformy algorytmiczno – programistycznej – Codeforces.
Poziom D to poziom finału Olimpiady Informatycznej Juniorów.
Zrobienie tego zadania daje piękny wpis w CV:
https://youtu.be/b5qWOUnM-fk?t=4809

——–
Zadanie omawia Michał Szeliga – laureat Olimpiady Informatycznej Juniorów:
https://youtu.be/OA8BeVFvaNU?t=830

——–
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

——-

#include <bits/stdc++.h>
using namespace std;
vector<int> sas[100001]; // Tablica sąsiedztwa
bool odw[100001]; //Czy dany wierzchołek był już odwiedzony DFS-em
int wy[100001]; // Wynik dla poddrzewa

void DFS(int v){
	if ((v == 1 && int(sas[v].size()) == 0) || (v != 1 && int(sas[v].size()) == 1)) wy[v] = 1; // Sprawdź, czy jesteś liściem. Jeśli tak, ustaw wynik na 1.
	odw[v] = true;
	for (int syn : sas[v]){
		if (odw[syn] != true){
			DFS(syn); //Po tym, wynik dla syna jest już gotowy
			wy[v] += wy[syn]; //Dodaj wynik poddrzewa syna do wyniku naszego poddrzewa			
		}
	}
}
int main(){
	int n; // n - ilość wierzchołków
	cin>>n;
	for (int i = 2 ; i <= n; i++){
		int ojciec;
		cin>>ojciec;
		sas[ojciec].push_back(i);
		sas[i].push_back(ojciec);
		//Dodajemy ojca do naszych sąsiadów, dodajemy siebie do sąsiadów ojca
	}// Wczytywanie krawędzi
	DFS(1); //Puszczamy DFS dla korzenia
	stable_sort(wy+1, wy+n+1); //Sortujemy tablicę wyników
	for (int i = 1; i < n+1; i++) cout<<wy[i]<<" ";
}
Kod C++ programu Decorate Apple Tree, który jest omówiony w powyższym filmie i który otrzymuje 100% 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz