Problem - LVP

general
1

Problem Statement#

You will be given a Directed Graph of N nodes (numbered 0 to N-1) and a dummy node X .

Each of the N nodes will have ONE outgoing edge to any of the other nodes or to X .

A path is Valid if it is edge disjoint , begins on the node ‘0’ and ends on the dummy node X .

You are allowed to change AT MOST one edge in the Directed Graph i.e take any node u in [0,N-1] and replace the existing edge (u->v) with an edge (u->x) where x can be any node of your choice (including dummy node!).

You have to maximise the length of the Longest Valid Path in the Resulting Graph.

Note: The graph may have self loops/cycles. An edge disjoint path is one in which no edges are repeated.

Input Format#

The first line of input has the number of Nodes N

The second line of input comprises N space separated Integers.

The ith no ‘y’ in second line denotes a directed edge between (i-1) and y . Dummy Node X is represented as -1

Sample Inputs

4

-1 -1 -1 -1

Ans = 2 ( Replace Node ‘0’s edge by adding edge from ‘0’ to any other node from [1,3] )

4

1 2 3 -1

Ans = 4 ( The Initial Graph is Optimal )

2

Let’s refer to Node 0 as the Root.

Let’s define Principal Chain as the list of nodes reachable from the Root.

You can solve the problem by observing that there will be two cases to consider :

  1. Root is stuck in a cycle :
    In this case you need to find the longest valid branch ( the longest branch which ends at the dummy node X ) which isn’t a part of the Principal Chain and attach it to one of the ends of the cycle .
    If there doesn’t exist any valid branch then you have no option but to replace Root’s edge to point to the dummy node.

alt text alt text

  1. Root isn’t stuck in a cycle :

In this case , you need to find the longest branch ( may or may not be valid ) and consider attaching it along the Principal chain or appending it to one of the ends of the Principal chain.

alt text alt text

alt text alt text

You can implement this by doing a DFS on the Transpose Graph ( Graph with Reversed Edges ) from each node in the Principal Chain and finding max depth reached.

The answer would be sum of number of nodes in the Principal Chain and Max Depth Reached over all dfs.

Since each node needs to be visited only once , you can ensure O(N) Complexity.

1 Like
3

PROBLEM LINK:#

Practice

Contest

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 :

  1. Path from node 0 or source is stuck in a cycle and not connected to sink node.
  2. 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.

  1. 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 ? :

  1. Check cycle Existence and calculate
    length of cycle, if it exists or
    length of chain, if it is directly
    connected to dummy node X
  2. 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.
  3. In case of cycle from source node
    just add length of cycle and maximum
    depth from dummy node X .
  4. 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.

AUTHOR’S & EDITORIALIST’S SOLUTIONS:#

Setter

Editorialist