B - バウムテスト

コメント歓迎です。
今回も深さ優先探索を使います。

初のグラフ問題でした。

問題

AtCoder 版！蟻本 (初級編) - Qiita より

arc037.contest.atcoder.jp

方針

この問題では、深さ優先探索で頂点を移動し、閉路があるかないかを判定します。

具体的には深さ優先探索で枝に沿って移動していき、一度訪問した頂点は訪問済みであることを記録します。

移動した先が探索済みの頂点だった場合に閉路ありと判定します。

閉路がなければ木としてカウントします。

初めてのグラフ問題で、枝情報をたどって移動する部分の実装が難しかったです。

移動するひとつ前の頂点は移動先から除外する必要がある点に注意が必要です。

処理の詳細はコード中のコメントに記載しましたので、それを参照してください。

コード(AC)

#include <iostream>
#include <vector>
using namespace std;

// 訪問履歴を記録するベクター
int N; // 頂点
int M; // 枝
int ans = 0; // 木の数
bool flag; // 閉路の有無を判定する変数

// 探索済みの頂点を記録するベクター
vector<bool> visited(100, false);
// 隣接行列
vector<vector<int> > connect(100,vector<int> (100, 0));

// 深さ優先探索
void dfs(int now, int previous) {
  // 枝に沿って移動した結果、探索済みの頂点についたら閉路有り
  if (visited[now]) {
    flag = false;
    return;
  }
  // 枝に沿って次の頂点へ移動
  else {
    visited[now] = true;
    for (int next = 0; next < N; next++) {
      // ひとつ前に探索した頂点は行き先から除外
      if (next != previous && connect[now][next] == 1) {
        dfs(next, now);
      }
    }
  }
  return;
}

int main() {
  // 入力
  cin >> N >> M;
  // 接続関係をベクターに記録
  int u, v;
  for (int i = 0; i < M; i++) {
    cin >> u >> v;
    connect[u-1][v-1] = 1;
    connect[v-1][u-1] = 1;
  }

  for (int i = 0; i < N; i++) {
    // 未訪問の頂点があればそこから探索開始
    if (!visited[i]) {
      flag = true;
      dfs(i, -1); // 閉路があるとflagがfalseになる
      if (flag) ans++;
    }
  }

  cout << ans << endl;
  return 0;
}