AtCoder ARC 37 バウムテスト ACできない理由がわからない

Question

前提・実現したいこと

AtCoder ARC 37 バウムテスト
https://atcoder.jp/contests/arc037/tasks/arc037_b
の問題がACできない。サンプルはすべてACし、自分で考えられるものをテストしても予想通りの結果が出る。

該当のソースコード

#include <bits/stdc++.h>
using namespace std;

bool loop = false;
void dfs(vector<vector<int>> A, int now, int before, vector<int> &vi){

if(vi[now]==1){loop=true;return;}
vi[now]=1;
for(int i=0; i<A[now].size(); i++){
if(before == A[now][i])continue; //直前は飛ばす
before = now;
now = A[now][i];
dfs(A,now,before,vi);
return;
}
}

int main() {

int N,M,ans=0;
cin>>N>>M;
vector<vector<int>> A(1000,vector<int>(0)); //入力を受け取って配列にする
vector<int> vi(1000,0);  //visitedの管理
for(int j=0; j<M; j++){
  int p=0,c=0;
  cin>>p>>c;p--;c--;
  A[p].push_back(c);
  A[c].push_back(p);
}
for(int k=0; k<N;k++){
  if(vi[k]==1)continue;
  dfs(A,k,-1,vi);
  if(!loop)ans++;
  loop=false;
}

cout<<ans<<endl;
}

試したこと

例題、と自分で思いついたもの何個か

Answer 1

4 4
1 2
1 3
1 4
3 4

このようなテストケースはどうでしょう
明らかに閉路を持つ連結成分しか存在しませんが、そのプログラムは「1」を表示します。

Comments

[taiyaki29]

ありがとうございます。おかしいところに気づけました。