k-tokitoh

2019-07-29

AtCoder Regular Contest 037 B

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

学んだこと