FastPrep
Problem · Graph

Detect a Cycle in Directed Hate Relationships

Learn this problem
● MediumArcesium logoArcesiumINTERNOA

Problem statement

There are n politicians labeled from 0 to n - 1. You are given a list of directed hate relationships hatePairs, where each pair [u, v] means that politician u hates politician v.

Return true if the directed graph formed by these relationships contains a directed cycle. Otherwise, return false.

A directed cycle exists when it is possible to start at a politician, follow one or more hate relationships in their stated direction, and return to the starting politician.

Function

hasDirectedHateCycle(n: int, hatePairs: int[][]) → boolean

Examples

Example 1

n = 4hatePairs = [[0,1],[1,2],[2,0],[2,3]]return = true

The relationships 0 -> 1, 1 -> 2, and 2 -> 0 form a directed cycle, so the result is true.

Example 2

n = 4hatePairs = [[0,1],[0,2],[1,3],[2,3]]return = false

Every relationship moves toward politician 3, and no path returns to an earlier politician. The graph has no directed cycle, so the result is false.

More Arcesium problems

drafts saved locally
public boolean hasDirectedHateCycle(int n, int[][] hatePairs) {
    // Write your code here.
}
n4
hatePairs[[0,1],[1,2],[2,0],[2,3]]
expectedtrue
checking account