Similar Pair, Graph algorithm problem

A pair of nodes,(a,b) , is a similar pair if both of the following conditions are true:

  1. Node a  is the ancestor of node b
  2. abs(a-b) <= k

Given a tree where each node is labeled from 1 to n, can you find the number of similar pairs in the tree?

Input Format

The first line  contains two space-separated integers n, (the number of nodes) and k (the similar pair qualifier), respectively.
Each line i of the n-1  subsequent lines contains two space-separated integers defining an edge connecting nodes Pi  and Ci, where node Pi is a parent to node Ci.

Constraints

Output Format

Print a single integer denoting the number of similar pairs in the tree.

Sample Input

5 2
3 2
3 1
1 4
1 5

Sample Output

4

Explanation

The similar pairs are (3,2),(3,1) ,(3,4), and (3,5), so we print 4  as our answer. Observe that (1,4) and (1,5)  are not similar pairs because they do not satisfy abs(a-b) <= k .

 

Solution in PHP

problem link Click Here

If any problem, feel free to comment or contact.

 

About Solution

Overview of Problem

Given a tree of n node and a number T find the number of pair (A,B) such that :

node A is the ancestor of node B
abs(A - B) <= T

Approch

First we need to traverse the tree using DFS so we need the root node and obviously the node which has no parent is the root node. Now as we traverse each node we will store it in a data stucture to keep track of all the ancestor for the next node but before that get the number of its own ancestors in the range [presentNode-T, PresentNode+T] and add it to the total pairs.

Data Structure

Now we need a data structure which can:

1. Insert a node as we travese the tree.
2. Remove a node as we return back.
3. Give number of nodes within the range [presentNode-T, PresentNode+T] which it have stored.

All of the above 3 operation needs to be done in log(N) time because N<=10^5 so we can take up our complexity to O(N log(N)). Binary Index Tree (BIT) is the a data structure which fulfills all of the above condition (There are other data structure like Segment Tree which can also be used).

We can do the above 3 operation by initialize all the index valve of BIT to 0 and then:

1. Insert a node by updating index of that node to 1
2. Remove a node by updating index of that node to 0
3. Get number of similar pair ancestor of that node by quary for sum of range in [presentNode-T, PresentNode+T]

If you are not familiar with BIT / Segement tree refer: BIT Tutorial / Segment Tree Tutorial

Use it to solve the problem in O(N log(N)). The DFS pseudo code will look like:

DFS(int node)
    similar_pair += bit_range_sum(max(1,node-t),min(n,node+t));
    bit_update(node,1);
    for(int i=0;i<al[node].size();i++)
        dfs(al[node][i]);
    bit_update(node,0);

 

Important Topics

To understand the problem and solution you have to know about Binary Index tree and Depth First Search. here is key points…

Depth First Search

Depth First Search (popularly abbreviated as DFS) is a recursive graph searching technique.

The Algorithm
While doing a DFS, we maintain a set of visited nodes. Initially this set is empty.
When DFS is called on any vertex (say ), first that vertex is marked as visited and then for every edge going out of that vertex, , such that is unvisited, we call DFS on .
Finally, we return when we have exhausted all the edges going out from .
Hence, if a graph is represented in the standard adjacency list form (a vector of vectors in C++), the C++ implementation follows:

void dfs(int node)  {
  seen[node] = true;
  for(int next: graph[node])  {
    if(not seen[next])  {
      dfs(next);
    }
  }
}

One may note that recursive calls imitate stack push and pop. Hence, DFS can also be implemented using stacks. In cases where the system stack size (which is used for recursion) is very limited, one might use a user-created stack to perform DFS within the memory limits.

The Complexity and Correctness
The above code provides a good angle to view at the complexity. Under no circumstance, DFS will be called twice on a node. For every node, we have iterations equal to the degree of that node. Hence the time complexity is simply sum of degrees of all the nodes which is .
If DFS is called on a node , and there exists a path then DFS will definitiely visit .
This can be proven as an induction on the path length of by observing that DFS indeed visits all nodes which have a direct edge from the first node and hence establishing the base case i.e. for path length = .

Applications
DFS is probably the most used graph-algorithm in programming contests. Many of the standard applications include – searching, counting connected components and their sizes, providing a useful way to number the vertices of a tree, finding bridges, finding euler path/tour and many others.
We’ll discuss about numbering the vertices of a tree.
Assume that you have a rooted tree and called a DFS on the root. Now, consider any arbitrary call the DFS makes, say its on node . Now, you can notice that DFS first visits all the nodes in ‘s subtree and only then visits any other node. Hence, if we number the nodes in the order they are visited, all the nodes in a particular subtree will come under a contigous range.
This kind of numbering is useful for questions which ask to modify all nodes in a particular node’s subtree. Doing this converts the problem to a range modification one which are pretty standard.

 

Binary Index Tree

// get cumulative sum up to and including i
int Get(int i) {
  int res = 0;
  while(i) {
    res += B[i];
    i -= (i & -i);
  }
  return res;
}

Coming to the update part, its just the reverse of the query. So the code will be:

// add val to value at i
void Set(int i, int val) {
  while(i <= N) {
    B[i] += val;
    i += (i & -i);
  }
}

 

 

Solution code in PHP here

 

 


fscanf($_fp,"%d %d",$n,$t);

function bit_q($bt,$i,$j){
 $sum=0;
 while($j&gt;0){
 $sum+=$bt[$j];
 $j -= ($j &amp; ($j*-1));
 }
 $i--;
 while($i&gt;0){
 $sum-=$bt[$i];
 $i -= ($i &amp; ($i*-1));
 }
 return $sum;
}

function bit_up(&amp;$bit,$n,$i,$diff){
 while($i&lt;=$n){
 $bit[$i] += $diff;
 $i += ($i &amp; (-$i));
 }
}

$al=array_pad([],100005,'0'); //adjacency list
$bit=array_pad([],100005,'0');

function dfs($node){
 global $bit,$n,$t,$similar_pair,$al;
 $similar_pair += bit_q($bit,max(1,$node-$t),min($n,$node+$t));
 bit_up($bit,$n,$node,1); 
 for($i=0;$i&lt;count($al[$node]);$i++){
 if ($al[$node][$i]&gt;0) {
 dfs($al[$node][$i]);
 } 
 }
 bit_up($bit,$n,$node,-1);
}

$similar_pair=0;
$root_node=array_pad([],100005,'0');

for($i=0;$i&lt;=$n;$i++){
 $root_node[$i]=true;
 $bit[$i]=0;
}

for($i=0;$i&lt;$n-1;$i++){
 fscanf($_fp,"%d %d",$x,$y);
 if(is_array($al[$x])){
 $al[$x][]=$y;
 }else{
 $al[$x]=[$y];
 }
 $root_node[$y]=0;
}
$r=-1;
for($i=1;$i&lt;=$n;$i++){
 if($root_node[$i]){
 $r=$i;
 break;
 }
}
dfs($r);

echo $similar_pair;


I am PHP problem solver at Hackerrank. I am preparing myself for PHP zend certification exam with Masud Alam sir.
I have completed few websites using LARAVEL, also have experience on WORDPRESS.

Leave a Reply

Your email address will not be published. Required fields are marked *