The longest path in a non-oriented and unweighted tree - in python

Question

I solve a problem in which I need to calculate the diameter of a tree. I know how to calculate that using two bfs, first find the farthest node and then the second bfs using the node that we found from the first.

But it’s hard for me to follow a very simple step - to make an adjacency list (dict in the case of python) from the input that I wrote for this code, but its not neat and not the best, can someone tell me how to do this effectively

Enter

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

An example :

-

12

thirteen

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

This 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 1

There are unnecessary checks in the code. For each edge AB, you just need to put B on the adjacency list A and A on the adjacency list B:

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, each node has an index between 1 and N, so you can use this fact and pre-populate with dictempty lists. This way you do not need to check if the key is in dictor not. Also make the code a little 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)

Answer 2

You use 0 instead of o in makedic in the first elif state. A correction has also been made for the undirected chart.

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] = [o]
             d[o] = [p]
        elif o not in d and p in d:
             d[o] = [p]
             d[p].append(o)
        elif p not in d and o in d:
            d[p] = [o]
            d[o].append(p)
        elif o in d:
            d[o].append(p)
            d[p].append(o)
    return d