Longest path in a undirected and unweighted tree - in python
<p>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.</p>

<p>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 </p>

<blockquote>
  <p><strong>Input</strong></p>
  
  <p>The first line of the input file contains one integer N --- number of
  nodes in the tree (0 &lt; N &lt;= 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 &lt;= u, v &lt;= N).</p>
  
  <p><strong>Example</strong>:</p>
  
  <p>8</p>
  
  <p>1 2</p>
  
  <p>1 3</p>
  
  <p>2 4 </p>
  
  <p>2 5 </p>
  
  <p>3 7 </p>
  
  <p>4 6 </p>
  
  <p>7 8</p>
</blockquote>

<p>My code is :</p>

<pre><code>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
</code></pre>

<p>Here is how I implemented bfs:</p>

<pre><code>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
</code></pre>

<p>You are using a <strong>0</strong> instead of <strong>o</strong> in makedic in first <em>elif</em> condition. Also made the correction for undirected graph.</p>

<pre><code>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
</code></pre>

python algorithm