Check Path Presence

Asked at Microsoft · Coding & Leetcode-style Questions · Difficulty: Medium

You are given an undirected graph consisting of N vertices, numbered from 1 to N, and M edges. The graph is described by two arrays, A and B, both of length M. A pair (A[K], B[K]) for K from 0 to M-1 describes an edge between vertex A[K] and vertex B[K]. Your task is to check whether the given graph contains a path from vertex 1 to vertex N going through all the vertices one by one in increasing order of their numbers. All connections on the path should be direct.

Loading the problem…