Is there a cycle?#4004

Is there a cycle? (Editorial)

Perform a depth-first search on the directed graph, treating it as disconnected. To do this, use an array $u se d$ to track the color of each vertex:

$u se d [v] = 0$ used[v] = 0 — vertex $v$ is white, meaning it has not been visited yet;
$u se d [v] = 1$ used[v] = 1 — vertex $v$ is gray, meaning it has been entered but its sons have not yet been fully processed;
$u se d [v] = 2$ used[v] = 2 — vertex $v$ is black, meaning both it and all its sons have been fully processed.

A cycle exists in a directed graph if, during depth-first search, we find an edge leading to a gray vertex.

Example

The graphs given in the problem statement have the following structure:

Algorithm implementation

Declare the adjacency matrix $g$ and the array $u se d$ to store the states of the vertices.

#define MAX 51
int g[MAX][MAX], used[MAX];

The function dfs performs a depth-first traversal of the graph, starting from vertex $v$ .

void dfs(int v)
{

Mark vertex $v$ as gray to indicate that we have entered it.

  used[v] = 1;

Iterate over all vertices that can be reached from vertex $v$ .

  for (int i = 1; i <= n; i++)

There is an edge from vertex $v$ to vertex $i$ if $g [v] [i] = 1$ g[v][i] = 1.

    if (g[v][i])
    {

If vertex $i$ is gray, then during the depth-first search we have encountered a gray vertex — a cycle is found.

      if (used[i] == 1) flag = 1;

If vertex $i$ is white, it means it has not been visited yet. Continue the depth-first search from it.

      else if (used[i] == 0) dfs(i);

If vertex $i$ is black, do nothing.

After processing all sons of vertex $v$ , mark it as black.

  used[v] = 2;
}

The main part of the program. Read the adjacency matrix.

scanf("%d", &n);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  scanf("%d", &g[i][j]);

Perform a depth-first search on the directed graph (as disconnected).

flag = 0;
for (i = 1; i <= n; i++)
  if (used[i] == 0) dfs(i);

Print the answer.

printf("%d\n", flag);

Java implementation

import java.util.*;

public class Main
{
  static int g[][], used[];
  static int n, flag;
  static void dfs(int v)
  {
    // mark vertex v as GRAY, make an entrance to v
    used[v] = 1;

    // we try to go from v to i, i = 1,2,...,n
    for (int i = 1; i <= n; i++)
      // if there exists an edge from v to i
      if (g[v][i] == 1)
      {
         // if vertex i is GRAY, we meet cycle
         if (used[i] == 1) flag = 1;
         // if vertex i is not visited, run dfs from there
         else if (used[i] == 0) dfs(i);
        // if vertex i is black (used[i] = 2), do nothing
      }
    // mark vertex v as BLACK, make an exit from v
    used[v] = 2;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new int[n+1][n+1];
    used = new int[n+1];

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      g[i][j] = con.nextInt();

    flag = 0;
    // run dfs on directed graph like on disconnected graph
    for (int i = 1; i <= n; i++)
      if (used[i] == 0) dfs(i);

    System.out.println(flag);    
  }
}

Java