Jakim sposobem wyszukuje się centroid grafu acyklicznego?
0
1
Centroid to taki wierzchołek w grafie, że jeśli skierujesz wszystkie krawędzie w stronę większej części grafu to wszystkie krawędzie będą do niego. Można jakoś Dfs'em zwracającym wielkość poddrzew - jeśli nie istnieje poddrzewo większe niż połowa grafu i nie ma nademną poddrzewa stanowiącego ponad pół grafu to ja jestem centroidem. Chyba nie trudne do napisania ;P