Cycle Detection in an Undirected Graph

Given an undirected graph represented by an integer \(n\) (the number of vertices) and an \(n \times n\) adjacency matrix \(A\), determine whether the graph contains a cycle. A cycle is a path of edges and vertices wherein a vertex is reachable from itself.

The matrix is symmetric for an undirected graph, and a value of 1 indicates the presence of an edge between vertices.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
A[0][0] A[0][1] ... A[0][n-1]
A[1][0] A[1][1] ... A[1][n-1]
...
A[n-1][0] A[n-1][1] ... A[n-1][n-1]

Here, the first line contains the integer \(n\), which is the number of vertices. Each of the following \(n\) lines contains \(n\) space-separated integers (0 or 1) representing a row in the adjacency matrix \(A\).

outputFormat

The output should be printed to standard output (stdout) and is a single line containing either "Yes" if the graph contains a cycle or "No" otherwise.

5
0 1 0 0 1
1 0 1 1 0
0 1 0 1 0
0 1 1 0 0
1 0 0 0 0

Yes