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

Solution 1:

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)

Solution 2:

You are using a 0 instead of o in makedic in first elif condition. Also made the correction for undirected graph.

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