【C言語】隣接行列でサイクルを作成する/しない

概要

隣接行列におけるサイクルを作成する、しないの条件をなかなか実装できず、有識者に教えていただいたのでメモとして記事にしようと思います。

コード

前提条件として、ひとつの頂点からは辺が１本の一方向にのみ生成されるという場合を考えています

qiita.rb

// j -> i へのパスが存在するか？
cur_node = j;
while (true) {
  if (cur_node == i) {
    // パスが存在する
    // do something
    break;
  }
  bool end = true; // while 終了フラグ
  for (int to = 0; to < n; to++) {
    // 辺が存在したら進む
    if (locked[cur_node][to]) {
      cur_node = to;
      end = false;
      break;
    }
  }
  if (end) break;
}