Graph related problem

Image for better understanding
Hi all,
You given a tree, not necessarily a binary tree. For every edge in it, you have to tell in how many paths that edge is present in. In other words, if you remove an edge, then how many vertices do not have a connection with each other (Either directly or indirectly). Please refer the image for better understanding of the ques.
I tried to solve it this way - For every edge, I performed 2 DFSs, one DFS from first vertex of the edge making sure I do not consider the second vertex and another DFS from the second vertex of the edge making sure to not include the first vertex of the edge.So, the answer now becomes the number of vertices visited in the first DFS multiplied with the number of vertices visited in the second DFS.
In other words ans= vertices visited in first DFS * vertices visited in second DFS.
Please note : first DFS is the DFS performed from the first vertex of the edge and the similar meaning applies for second DFS. But unfortunately, it timed out yielding only a partial score. This is an interview question so I do not have a link to share.
Hope my question is clear.
Thank you.

I have a doubt-

If its a tree, then there are only n-1 edges. then shouldnt the answer simply be equal to number of nodes below the edge?

EDIT- Okay, essentially the problem is same. What I would do is, traverse the graph once to store “how many children does this node have in total +1 [to include that node as well]” per node.

To do this quickly, we can go like, assign leaves 1. Parent’s number is =Sum of number on all of its child.

(eg, a tree like-

1 2
1 3

will have 1 labelled on leaves 2,3 and (1+1[sum of no. on children] +1 [to include 1])= 3 on node 1.)

Now the answer is simply the product of the (number on node) x (Total nodes- number on that node)

2 Likes

This is just simple combinatorics. Removing the edge (u, v) from a tree, will split it into two subtrees. A path in a tree is uniquely defined by their endpoints. So all the paths that start from a node in the first and end in the second subtree are now not connected. And this are |subtree(u)| \cdot |subtree(v)| many.


You can easily express |subtree(v)| = |tree| - |subtree(u)|.

So you only need to compute the sizes of all subtrees. You can do this with dfs and dp:

int dfs(int v, int p)
{
    int size = 1;
    for (int u : adj[v]) {
        if (u != p)
            size += dfs(u, v);
    }
    // now size contains the size of the subtree rooted at v
    // do something with it. 
    return size;
}

You only need to call this code once. It will calculate the size of each subtree.

2 Likes

Please check the description @vijju123. I updated it.

Yeah. Please look at my updated description to read the approach I took and its result. Thank you.

Exactly! Thats the best solution i could think of :slight_smile: