AtCoder Beginner Contest 204 C - Tour
公式解説を自分で理解するために注記を記入。
#include<bits/stdc++.h> using namespace std; const int MAX_N = 2000; vector<vector<int>>G; bool temp[MAX_N]; // 到達できたか?フラグ void dfs(int v) { // 深さ優先探索 : dfs if (temp[v])return; // 既に到達したことがあれば return temp[v] = true; // 到達した。 for (auto vv : G[v])dfs(vv); // 到達した所からその子供全部へ dfs } int main() { int N, M; cin >> N >> M; G.resize(N); // 2次元配列 : G にツリー構造生成 for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; G[a - 1].push_back(b - 1); } int ans = 0; // 到達合計 // 全部の要素に対して dfs を行う。 for (int i = 0; i < N; i++) { // 到達できたか?フラグを一度全部クリア for (int j = 0; j < N; j++)temp[j] = false; // dfs実行 dfs(i); // 到達数を集計 for (int j = 0; j < N; j++)if (temp[j])ans++; } cout << ans; }