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

purple_dreams's blog

By purple_dreams, history, 8 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

You need DFS. When you are at a node v and want to call dfs(u) , set parent[u] = v.