ABC054: C - One-stroke Path

問題

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

解法

なので、DFSで全探索すれば良い。

int N, M;
vector<vector<int>> G;
int ans = 0;

void dfs(int curr, std::set<int>& st) {

  if (st.size() == N) {
    ans++;
    return;
  }

  rep(i, G[curr].size()) {
    int next = G[curr][i];
    if (st.count(next)) {
      continue;
    }
    st.insert(next);
    dfs(next, st);
    st.erase(next);
  }
}

int main() {

  cin >> N >> M;
  G.resize(N);
  rep(i, M) {
    int a, b; cin >> a >> b;
    G[a - 1].push_back(b - 1);
    G[b - 1].push_back(a - 1);
  }

  set<int> st; st.insert(0);
  dfs(0, st);

  std::cout << ans << "\n";
  
  return 0;
}

感想

辺の数を読むのを忘れてで処理していたので、サンプルが合わずに少し時間がかかった。