PROBLEM LINK:
Author: Abhijeet Jha
Tester: Teja Vardhan Reddy
Editorialist: Aswin Ashok
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
A tree containing N nodes and rooted at node 1 is given. On each node of the tree, there is a monkey having information about a graph G.
G is a graph containing N nodes. The information contained on each node is an edge of the graph G .
Now for every node X, consider the path from root to X. You have to collect the information about edges from this path and construct a new graph G’. The constructed graph G’ will be a sub-graph of graph G obviously.
For each node you need to find the number of connected component in graph G’.
EXPLANATION:
Given a tree with N nodes rooted at 1. Each of the tree nodes contain
an edge of a Graph G with also has N nodes. Each path in the tree gives some of
the edges of the graph G and the graph formed by this is a sub-graph of G and let us
call it G’. We are asked to find number of connected components in G’ (s) formed
by all the paths from 1 to i (where i=1 to N).
SOLUTION:
Let us initialize the number of connected components in G’ as N, let’s call it cc. We
can do a DFS from the node 1 of the tree. As and when we reach a node i we can
check if the edge contained in the node connects two disjoint components in G’
using Union Disjoint Find. If yes we can reduce cc and store the answer for path 1
to i in answer[i] and store the roots of nodes in the edge and do union operation.
When the DFS retraces back we can use the stored to roots to see if the union
operation at that particular node reduced cc. If yes we can undo the union
operation.
Once the DFS completes get we the required answers.
TIME COMPLEXITY
Using Union Disjoint Find we can find the roots in O(logN) and do
union or undo it in O(1). There are N nodes in the tree so Overall time complexity
is O(NlogN).
SOLUTIONS LINKS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.