Exercise: Graphs

Solve a task to find if an AdjacencyMatrix has a universal sink.

We'll cover the following

Task

A universal sinkA universal sink, v, is also sometimes called a celebrity: Everyone in the room recognizes v, but v doesn’t recognize anyone else in the room. in a graph GG is a vertex that is the target of n1n − 1 edges and the source of no edges. Design and implement an algorithm that tests if a graph GG, represented as an AdjacencyMatrix, has a universal sink. Your algorithm should run in O(n)O(n) time.

Sample input

The sample input will be as follows:

(0, 4)
(1, 4)
(2, 4)
(3, 4)
(4, 4)

Expected output

The expected output will be as follows:

Universal Sink not found.
Vertex 4 is a Universal Sink in the graph.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy