Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

How to represent Trees?

Правка en1, от purple_dreams, 2017-06-13 13:33:51

I am a beginner so soory if the question sound too easy. If in the question it is given there are n cities and n-1 roads connecting them, solve something. The input is given as n (the number of cities) followed by n-1 roads (format u v meaning that there is a bidirectional road from u to v). How do I represent such a tree. I want a parent array to store the parent of each node. But how do I get the parent of each node assuming the root of tree is 1 always. An adjacency list stores for each vertex all the neighbouring vertices but it doesn't have any info about parent. Now if I want to find LCA in such a case, I need the parent array. So how to go about that. Thanks.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский purple_dreams 2017-06-13 13:33:51 697 Initial revision (published)