dfsで閉路検出 D - Subway

f:id:peroon:20200902182551p:plain

解法

  • 閉路が1つだけあることが決まっているので、dfsして再訪した点があれば、それは閉路内の点
  • dfsしながら親を記録しておけば、閉路発見時に親をたどって閉路の点が全てわかる
  • 閉路内の点は距離0
  • 閉路内の各点を始点として閉路以外の点方向にdfs2をして距離を求めればよい(下記イメージ)

f:id:peroon:20200902183054p:plain

この記事は何

  • dfsで閉路を見つけてそのパスを求めたい時の参照用

excerpted code

int n,x,y;
int f,s; // loop start & end
int ans[3005];
int pred[3005]; // parent
vector<int> v[3005];
bool used[3005];
bool closed[3005];

// 答え用
void dfs2(int x,int d,int p=-1){
  ans[x]=d;
  for(ll to : v[x]){
    if(to==p)continue;
    if(!closed[to]) dfs2(to, d+1, x);
  }
}

// 閉路検出用
void dfs(int x,int y){
  pred[x]=y;
  used[x]=1;
  for(ll to : v[x]){
    if (to==y) continue;
    if (used[to]==1) {
      // revisit
      s=x;
      f=to;
      debug(s,f);
      return;
    }
    dfs(to,x);
  }
}
int main(){
    cin>>n;
    rep(i,n){
      cin>>x>>y;
      x--;y--;
      v[x].push_back(y);
      v[y].push_back(x);
    }

    dfs(1,-1);
    swap(f,s);
    // 閉路を辿る
    while (s!=f) {
        closed[s]=true;
        s=pred[s];
    }
    closed[f]=true;
    
    rep(i,n){
      if (closed[i]==true) dfs2(i,0);
    }
    VI A;
    rep(i,n){
      A.push_back(ans[i]);
    }
    print_vector(A);
}