Cody

Problem 1170. Count the Number of Undirected Cycles in a Graph

Given a symmetric adjacency matrix, determine the number of unique undirected cycles.

For example, the graph represented by adjacency matrix

A = [
  0 1 1 0 1
  1 0 1 1 0
  1 1 0 1 1
  0 1 1 0 0
  1 0 1 0 0];

has 6 cycles. They are:

[1 -> 2 -> 3 -> 1]
[1 -> 3 -> 5 -> 1]
[2 -> 3 -> 4 -> 2]
[1 -> 2 -> 4 -> 3 -> 1]
[1 -> 2 -> 3 -> 5 -> 1]
[1 -> 2 -> 4 -> 3 -> 5 -> 1]

The input is an adjacency matrix of 0s and 1s, and the output should be the number of unique (simple) undirected cycles in the graph.

Solve

Solution Stats

38.46% Correct | 61.54% Incorrect
Last solution submitted on Nov 28, 2018

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author3