ABC016 C - 友達の友達

問題

atcoder.jp

コード

using Graph = vector<vector<int>>;
 
Graph G;
vector<int> ct;
vector<bool> seen;
 
void dfs(int pre, int c, int p,int d){  //pre:スタート, c:探索ノード, p:親, d:深さ
  if(d == 2){
    for(auto i:G[c]){
      if(i == pre) return;
    }
    if(seen[c]){
      ct[pre]++;
      seen[c] = false;
    }
  }else{
    for(auto j:G[c]){
      if(p != j){
        dfs(pre,j,c,d+1);
      }
    }
  }
}
 
int main(){
  //cout.precision(10);
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int N,M; cin >> N >> M;
  
  G.resize(N);
  ct.assign(N,0);
  
  
  rep(i,M){
    int a,b;
    cin >> a >> b;
    --a;--b;
    G[a].PB(b);
    G[b].PB(a);
  }
  
  rep(i,N){
    seen.assign(N,true);
    dfs(i,i,-1,0);
    cout << ct[i] << endl;
  }
 
}

解法

深さ2までのdfsを実装した。違う経由点から同じ友達の友達に行く経路でダブルカウントしてしまっていたので、seenを導入した。