PROBLEM LINK:#
Author: Animesh Fatehpuria
Editorialist: Pradeep Joshi
DIFFICULTY:#
Easy-Medium
PREREQUISITES:#
DFS
PROBLEM:#
Given a graph having one source and sink node, where each node has exactly one edge except sink node . We are allowed to replace maximum one edge by any other and need to find longest valid path . A valid path is a path from source to sink which has no repeated edges and vertices. The graph may have self-loops/cycles .
QUICK EXPLANATION:#
======================
There are two cases :
- Path from node 0 or source is stuck in a cycle and not connected to sink node.
- Path from source node is connected to sink node.
Calculate answer for both cases differently and focus on edge cases.
EXPLANATION:#
===============
Let’s refer to Node 0 as the Source.
Let’s define Principal Chain as the list of nodes reachable from the Source.
You can solve this problem by observing that there will be two cases which we need to consider :
1) Source is stuck in a cycle :
Our final goal is to find longest valid branch from source node to sink node . As in this case source is stuck in a cycle , we need to disconnect this cycle and need to make connectivity with sink node or dummy node X . We can connect any node of cycle to directly dummy node or any other node which is directly or indirectly connected to dummy node .Since we want to find longest valid path, so we must disconnect the edge which makes cycle in principal chain by connecting to source node and this removed edge must be attached to longest chain connected to dummy node . If no such chain is found then directly attach it to dummy node .
Answer will be length of Cycle + length of longest chain which connects dummy node X.
-
Source isn’t stuck in a cycle :
As source is not stuck in cycle it must connects to sink node i.e. dummy node X . Now we can still remove one edge from somewhere in the graph and possibly make this source to sync path longer than current one . One thing we need to keep in mind that we must have connectivity from source to sink .
How to increase the length of current path ?
Length of current path can be increased by disconnecting the current path from any node except source or sink and attach it to some node which has already connectivity with sink node with greater length. The simple way to do is that from each node, from source node to sink node, except source node, find longest path possible for these nodes but this path should not contains any node from principal chain except itself.
The answer would be sum of number of nodes in the Principal Chain and Max Depth Reached over all nodes in principal chain except source .
How to Implement ? :
- Check cycle Existence and calculate
length of cycle, if it exists or
length of chain, if it is directly
connected to dummy node X - Mark all nodes of path from source
to sink and calculate maximum depth
path reached by each node except
source and this path should not
contain any marked nodes. Maximum
depth can be calculated by doing dfs
in reversed graph. - In case of cycle from source node
just add length of cycle and maximum
depth from dummy node X . - In case of no cycle from starting node add length of
principal chain and maximum depth achieved
over all nodes in principal chain
except source .
Since each node needs to be visited only once , you can ensure O(N) Complexity.