john smith - 1 year ago 125
Python Question

# Longest path in a undirected and unweighted tree - in python

I am solving a problem in which I need to calculate the diameter of the tree.I know how to calculate that using 2 bfs first to find the farthest node then do second bfs using the node we found from the first one.

But I am having difficulty to implement a very simple step - making a adjacency list (dict in case of python) from the input I have written a code to this but its not tidy and not the best can someone tell how to do this efficently

Input

The first line of the input file contains one integer N --- number of
nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges
of that tree --- Each line contains a pair (u, v) means there is an
edge between node u and node v (1 <= u, v <= N).

Example:

8

1 2

1 3

2 4

2 5

3 7

4 6

7 8

My code is :

``````def makedic(m):
d = {}
for i in range(m):
o, p = map(int, raw_input().split())
if o not in d and p not in d:
d[p] = []
d[o] = [p]
elif o not in d and p in d:
d[o] = []
d[p].append(o)
elif p not in d and o in d:
d[p] = []
d[o].append(p)
elif o in d:
d[o].append(p)
# d[p].append(o)
elif p in d:
d[p].append(o)
return d
``````

Here is how I implemented bfs:

``````def bfs(g,s):
parent={s:None}
level={s:0}
frontier=[s]
ctr=1
while frontier:
next=[]
for i in frontier:
for j in g[i]:
if j not in parent:
parent[j]=i
level[j]=ctr
next.append(j)
frontier=next
ctr+=1
return level,parent
``````

Answer Source

There are unnecessary checks in your code. For each A - B edge you just have to put B in A's adjacency list and A in B's adjacency list:

``````d = {}
for i in range(m):
u,v = map(int, raw_input().split())
if u in d:
d[u].append(v)
else:
d[u] = [v]
if v in d:
d[v].append(u)
else:
d[v] = [u]
``````

According to the question every node has an index between 1 and N so you can use this fact and pre-populate the `dict` with empty lists. This way you don't have to check whether a key is in the `dict` or not. Also make the code a little bit shorter:

``````N = input()
d = { i:[] for i in range(1, N+1) }
for i in range(N):
u,v = map(int, raw_input().split())
d[u].append(v)
d[v].append(u)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download