競プロ日記

問題
ACコード
WAコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst) : src(src), dst(dst) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector;
using Graph = vector;

void edges_to_graph(Graph &graph, const Edges &edges, const int vertices, const bool directed = true) {
  graph.resize(vertices);
  for (const auto &e : edges) graph[e.src].emplace_back(e);
  if (!directed) for (const auto &e : edges) graph[e.dst].emplace_back(Edge(e.dst, e.src, e.weight));
}

void dfs(Graph &g, int v, vector &route, vector &checked, bool &ok, const vector &vlist, const int len) {
  if ((int)route.size() >= len - 1) return;
  route.push_back(v);
  if (checked[v]) {
    ok = true;
    return;
  }
  checked[v] = true;
  for (const auto &e : g[v]) {
    if (!vlist[e.dst]) continue;
    dfs(g, e.dst, route, checked, ok, vlist, len);
    if (ok) return;
  }
  route.pop_back();
  checked[v] = false;
}

Graph graph;
int main(void) {
  int n, m;
  cin >> n >> m;
  Edges edges(m);
  rep (i, m) {
    int a, b;
    cin >> a >> b;
    edges[i] = {--a, --b};
  }
  edges_to_graph(graph, edges, n);
  vector route(n + 1);
  iota(all(route), 0);
  bool changed = true;
  int  len = INT_MAX;
  while (changed) {
    changed = false;
    vector vlist(n);
    rep (i, route.size() - 1) vlist[route[i]] = true;
    rep (i, route.size() - 1) {
      vector checked(n);
      bool ok = false;
      vector newroute;
      dfs(graph, route[i], newroute, checked, ok, vlist, len);
      if (ok) {
        int start = newroute.back();
        rep (j, newroute.size()) {
          if (newroute[j] == start) {
            route = vector(newroute.begin() + j, newroute.end());
            len   = newroute.size() - j;
            break;
          }
        }
        changed = true;
        break;
      }
    }
  }
  len = len != INT_MAX ? len - 1 : -1;
  cout << len << endl;
  rep (i, len) cout << route[i] + 1 << "\n";
  return 0;
}

コンテスト参加中は考えるべきではないと判断した問題だが、正解となるグラフがどのようになるのか分かれば全体の理解は簡単だった。
BFSでの解説が多く見つかったが、DFSの方が書きやすいし制約的にも大丈夫そうなのでそちらで実装した。
直感的にはBFSの方がやりたいことにあってそうだし早そう。
DFSでACまで持っていったが、すんなり理解したわりに実装はバグらせまくってしまった。

WAコードの一番の問題は、グラフが連結だと思いこんでしまっていたことも含む、グラフへの理解のなさ。
工学系出身なので理系ではあるものの、グラフ理論なんてものはやっていない(たぶん)ので、競プロである程度勉強したとは言え、やはりグラフと言えば全ての頂点が繋がっているという固定概念が抜けきれていない。
孤立した点があるならそんなのグラフじゃないじゃん・・・という話だ。
それに気づくまでに時間がかかりすぎた。

グラフが連結であれば、入次数が0の頂点がなければ必ず閉路があると言える。
だが、逆に入次数が0の頂点があれば必ず閉路がないとは言えない。
グラフが連結だと思い込んだ上で、これも言えると思い込み、-1を出力する条件をグラフ全体の入次数のみで判定してしまっていた。
これがWAコードの大きな間違い。
他にも少し間違っている部分はあった。

まず、DFSで子→親への遷移を止めているところ。
普通のDFSならこれをしないのは無限ループの元だが、閉路を見つけるという目的に限ってはこの遷移を止めてしまうと2頂点の閉路を見つけられなくなってしまう。

次に、経路として取った頂点の順番を記録した配列と、その頂点を通ったかどうかO(1)で判定するための配列を別々に取っていたのだが、DFSの帰りに順番の配列の方はpopしたのに、判定の配列の方を変更するのを忘れていた。
完全に頭から抜けていた。
似たようなものはまとめた方が間違いなく良いのだが、順番の記録と判定をうまく一気に行えるような方法はないのかなぁ。

最後に、WAコードの方針なら間違いではないのだが、方針を変えたときに一緒に変えるべきだと気づけなかった部分。
閉路の長さの管理方法の問題。
長さ用の変数と閉路の頂点を格納する配列を別に取っていた。
基本的な方針として、閉路に含まれる頂点+終点になる頂点1つ(始点と被る)の配列を用いて、閉路を縮められないかを確認していた。
この場合、全ての頂点を用いる閉路が最短だとしても、頂点数がN+1より大きくなることはない。
そこで、長さの初期値をN+1にしてN以下の閉路を探していくようにすれば、(WAコードの方針なら)-1になることはないと分かっているので、閉路の初期値に全ての頂点を含めることで、N以下の閉路を見つけられなくてもそのまま出力してうまくいくような実装にしていた。
正しい方針では-1であるかどうかは事前に調べられないので、長さがN+1から変わっていない=閉路を見つけられていない、で判定するようにした。
しかしそうすると、実際に全ての頂点を使った閉路が存在するのか、あるいは閉路が存在しなくて初期値のままになっているのかが、正しく判定できない状態になってしまっていた。
この問題は、長さの変数を「現在の閉路の長さを表す変数」というよりも、「今まで見つけた最短の閉路の長さ」というような役割に変えることで解決した(ほぼ同じような役割だが)。
すごく単純な話だが、長さ用の変数は用意しなくても、Vectorならsize()でO(1)で取得できる。
それなのになぜわざわざ長さ用の変数を用意したかというと、ループの条件式や中身で何度も関数が呼ばれるのを避けたかったからである。
O(1)とは言っても関数呼び出しのオーバーヘッドはあるわけで、そういうの嫌だなぁととても思うタイプ。
そもそもなぜC++を好んで使っているかというと、競プロ関係なく、プログラムは速度至上主義的な考え方だからである。
細かい部分を気にするなら細かい部分まで気を配れる実力つけろという反省。


明らかにDAGが関係してくる問題だと思ったのだが、トポロジカルソートは実装できなかった。
だが閉路を見つけて色々するような経験を積めたので、DAGとかトポロジカルソート関連の問題が出てきたときに生きてくれるだろうと思う。