Building a tree from edges

general
, ,
1

Hi everyone.

I’ve been looking for a solution the whole day but I can’t find an algorithm to solve the following.
In most of the problems refereed to “Trees” in Codechef the inputs are N-1 lines where each line has numbers U and V representing an edge. My question is, does anyone know an algorithm to build a tree only with the set of the edges?

Note. Look that when the numbers U V are given they don’t have an special order. (1,2) does not mean that 1 is the parent of 2 or viceversa.

Thank you very much

2

If it is undirected, there isn’t a special order. Because if 1 and 2 is connected with an edge, any one maybe anyone’s parent thinking of the perspective one wants to see the tree. Usually a root is given, just maintain this and start a dfs from the root. You don’t have to worry about order.

If it’s a directed tree, it’ll be given in the description how it is described in input.

3

Tree is a Graph, such that there is no cycle in it. So you can follow all the ways, one use to represent Graph:

1). Adjacency List(Most Preferable)

2). Adjacency Matrix.

Now How to built Tree only with set of edges ??.

–> Make Array A of Size N.[1…N]. Data Type of Array is : Pointer to LinkList.

DataMembers of LinkList:

if graph is weighted: int V, int Weight.

if graph is Unweighted: int V.

–>The LinkList Pointed by ith index of Array A represents all edges which has one of the endpoint as i.

–> Now for each edge U—V do:

A.add(V)
A[V].add(U)

–>This is called Adjacency List Representation of Graph.

For other ways to construct Graph please read :

Link : Implementation

4

The trouble with those adjacency lists is that the queries are really slow… For example if I need to find the path between two nodes it takes O(N) time almost all of the times, instead of that, If I represent the undirected graph as a rooted tree, the worst case takes O(N) time and that’s only when the graph is a single path.

5

Well i dont know you want to perform queries on Nodes(as you have not mentioned that part in question):
I also get stuck at the same thing of answering Queries between nodes of tree and have already asked a question about it yesterday in Codechef: It will help you to start learning about how to answer those kind of queries in Least Time.

Question Link