Submission #75068608

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
vector<bool> seen;
void dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする
    
    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        dfs(G, next_v); // 再帰的に探索
    }
}
int main() {
    int64_t N;
    cin >> N;
    int64_t M;
    cin >> M;
    int64_t ans = 0;
    Graph G(N);
    for (int64_t i = 0; i < M; i++) {
      int64_t a, b;
      cin >> a >> b;
      G[a-1].push_back(b-1);
    }
     // 頂点 0 をスタートとした探索
    seen.assign(N, false); // 全頂点を「未訪問」に初期化
    dfs(G, 0);
    for (int i = 0; i < N; i++) {
      if (seen.at(i) == true) {
        ans++;
      }
    }
    cout << ans << endl;
    return 0;
  }

Submission Info

Judge Result