GRAPHS

NODES AT EVEN DISTANCE

Given a connected acyclic graph with 'n' nodes and 'n-1' edges , find out the number of pair of nodes that are at even distances from each other.

Sample input:

3     (N denoting the number of nodes in graph.)

1 2 2 3  ( N-1 pair of nodes xi , yi denoting that there is an edges between them.)

Output:

1

 Only pair is (1,3) where distance between them is 2.

Hint :

We can choose any node as root and apply depth first traversal from it.While DFS,store the distance of each node from root in an array.Now nodes at even distance can be choosen as following: 

Choose 2 nodes that are at even distances from the root or choose 2 nodes at odd distances from the root.

Let E be the total number of even distance nodes from the root.

Let O be the total number of odd distance nodes from the root.

Number of pair of nodes that are at even distance from each other =

EC2 + OC2

Program: [Java]

import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
     int V;
     LinkedList<Integer> alist[];
     int dist[];
         public Graph(int n)
         {
               V=n;
               alist=new LinkedList[n];
           

               for(int i=0;i<n;i++)

                    alist[i]=new LinkedList<Integer>();
            dist=new int[n];
         }
   

         void addedge(int s,int e)
         {
              alist[s].add(e);

              alist[e].add(s);
         }
       

         void DfsUtil(int v,boolean[] visited)
        {
              visited[v]=true;
              Iterator<Integer> it=alist[v].iterator();
              while(it.hasNext())
              {
                   int n=it.next();
                   if(!visited[n])

                   {

      dist[n]=dist[v]+1;

      DfsUtil(n,visited);

                   }
              }

         }

        void Dfs()
        {
                 boolean[] visited=new boolean[V];
                for(int i=0;i<V;i++)
                {
                      if(!visited[i])
                           DfsUtil(i,visited);
                }

        }
}

class GFG {
      public static void main (String[] args) {
      Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        Graph g=new Graph(n);
        for(int j=0;j<n-1;j++)
        {
              int src=scan.nextInt();
              int des=scan.nextInt();
              g.addedge(src-1,des-1);
        }
             g.Dfs();
             int[] d=g.dist;int odd=0,even=0;
            for(int j:d)

            {

                 if(j%2==0)

                         even++; 

                 else 

                         odd++;

            }
           System.out.println(even*(even-1)/2 +odd*(odd-1)/2);
    }
}