【ABC備忘録】再帰によるDFSの基本(java)

ABCのD396を例に、再帰によるDFSの基本についてまとめます。

単純パスとしてあり得るのは、最初が1、次に残りのN-1個から一つ選び...という操作を繰り返し、O((N-1)!)となり、N=10の場合にこれは10^6程度となり、全探索が可能になる。よってDFSによって全探索を行う。

  public static void dfs(int temp , long xor ,long label){
    xor = xor ^ label;
    visited[temp] = true;
    if (temp == N){
      visited[temp] = false;
      if (ans > xor){
        ans = xor;
      }
      return;
    }
    for (int i = 0 ; i < pointList[temp].size() ; i++){
      int next = pointList[temp].get(i);
      long nextLabel = labelList[temp].get(i);
      if (!visited[next]){
        dfs(next,xor,nextLabel);
      }
    }
    visited[temp] = false;
  }

これがdfsの関数である。再帰によるdfsの特徴としては、自動で状態を保持してくれることがあげられる。
最後のvisited[temp] = false;によって、一つのルートが限界までに行き切った時に、その点のvisitedをリセットしてから一つ上に戻ることができる。