AtCoder Regular Contest 037 B
コード
他の回答をみつつ書いた。
#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 100
vector<int> graph[MAX_N];
bool visited[MAX_N];
// あるノードiと1つ前に訪れたノードprevを渡すと
// - iから行けるノードを全て配列visitedに記録する
// - iから行けるパスが閉路をもっていればfalseを、閉路をもっていなければtrueを返す。
bool dfs(int i, int prev) {
// 既に訪れられているノードなら、falseを返す（閉区間であることを表す）
if (visited[i]) return false;
// 訪問済みとしてマークする
visited[i] = true;
bool ret = true;
// 隣接するノードのうち、
for (int j = 0; j < graph[i].size(); j++) {
// 1つ前に訪れたノード以外について、
if (graph[i][j] == prev) continue;
else {
// 再帰的にdfsを呼び出す
if (!dfs(graph[i][j], i)) ret = false;
}
}
return ret;
}
int main() {
// ノードとエッジの数を入力から受け取る
int N, M;
cin >> N >> M;
// 訪問状況を表す配列を初期化する
for (int i = 0; i < N; i++) {
visited[i] = false;
}
// 入力から隣接リストを作成する
int u, v;
for (int i = 0; i < M; i++) {
cin >> u >> v;
graph[u-1].push_back(v-1);
graph[v-1].push_back(u-1);
}
// ノード1つにつき1ループする
int count = 0;
for (int i; i < N; i++) {
// もし訪問済みでないならば
if (!visited[i]) {
// そのノードを起点としてdfsを呼び出す
if (dfs(i, -1)) count++;
}
}
cout << count << endl;
}
