 # Building a tree from edges

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

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.

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

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.

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)
``````

–>This is called Adjacency List Representation of Graph.