Regarding implementation of tree

tree

#1

what is the correct way to implement tree in codechef problems ?
when i implement it using adjacency list with undirected egdes
it passes, but for directed edge it shows wrong answer.
Can anyone help me out ?


April19 - Problem Discussion
#2

directed and undirected are completely different

it has nothing to do with codechef

the ques was designed for undirected graph

thus inputs were not like :-

u v

then u is parent and v is child

u were supposed to connect u and v

then determine who is the parent by any method (dfs for eg)


#3

Here, u and v denote that an edge exists between u and v (if you’re talking about SJ1, SUBREM, MINXOR) … you have to do something like this
adjList[u-1].pb(v-1);
adjList[v-1].pb(u-1);
(u-1 and v-1 because it’s 1 indexed)
(Heat pb means push_back)
You then run a function using stack to get the parent child relation for every node …


#4

If it doesn’t work with undirected edges then you should convert your undirected graph(or tree) to directed graph(or tree).
undirected edge from u to v == ( directed edge v to u + directed edge u to v)
Hence you will insert two directed edges for each edge of undirected graph.
Hope this helps :slight_smile: .


#5

Like in the problem SUBREM it is mentioned that there is an edge between u and v.
How can i figure out that it is undirected or directed one?


#6

consider edge as undirected unless they mention its directed.