Company: KLA
Difficulty: medium
Cycle Detection in a Graph Problem Description Given n number of nodes, numbered from 1 to n , and m number of directed edges. The edges are provided as a list of pairs of integers, where each pair [u,v] in the edges list represents a directed edge from node u to node v . Find the total number of nodes out of n that can be chosen such that none of them have a cyclic dependency on each other. Examples Example 1: Input: n = 2, m = 2, edges = [[1,2],[2,1]] Output: 1 Explanation: Nodes 1 and 2 form a cycle (1 -> 2 -> 1). If we choose both nodes {1, 2}, they have a cyclic dependency. However, we can choose a single node, for example, {1}, which forms an acyclic set. Similarly, we can choose {2}, which also forms an acyclic set. The maximum number of nodes we can choose such that none of them have a cyclic dependency on each other is 1.