Orient Graph - Linkedin Online Assessment IIT Kanpur

You are given a graph with n vertices numbered from 1 to n. The graph contains m edges. However, for every edge, only its two endpoints are given. The direction of each edge is unknown and may be chosen arbitrarily.

You are also given an ordering of all vertices representing a traversal.

Determine whether it is possible to assign a direction to every edge such that the given ordering is a valid traversal of the graph.

Print "YES" if such an assignment exists; otherwise print "NO".

Example 1:

Input:[4,3,[1,2,3],[2,3,4],[1,2,3,4]]

Output:YES

Example 2:

Input:[4,2,[1,3],[2,4],[1,2,3,4]]

Output:NO

Constraints:

1 ≤ n ≤ 2 × 10^5 n - 1 ≤ m ≤ 2 × 10^5 1 ≤ ui, vi ≤ n The traversal contains every vertex exactly once.

solution.cpp

Run code to see test results

00:00 / 69:42

Orient Graph - Linkedin Online Assessment IIT Kanpur

MediumMed•741 views

You are also given an ordering of all vertices representing a traversal.

Determine whether it is possible to assign a direction to every edge such that the given ordering is a valid traversal of the graph.

Print "YES" if such an assignment exists; otherwise print "NO".

Example 1:

Input:[4,3,[1,2,3],[2,3,4],[1,2,3,4]]

Output:YES

Example 2:

Input:[4,2,[1,3],[2,4],[1,2,3,4]]

Output:NO

Constraints:

1 ≤ n ≤ 2 × 10^5 n - 1 ≤ m ≤ 2 × 10^5 1 ≤ ui, vi ≤ n The traversal contains every vertex exactly once.

MediumMed•741 views

Time Complexity

Space Complexity

Asked at

Author: Amit Dayal

Software Engineer

Expert in Data Structures & Algorithms. Building tools to help developers crack FAANG interviews.