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;
}