問題

B – バウムテスト

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/01/28 UnionFindでやろうとしたが、二重で .leader() を使う発想が思いつかず。

解法1

1. Union-Find 使った閉路判定。
2. \(u_{i}\) と \(v_{i}\) を merge するまえに それぞれの leader を確認する。
3. \(u_{i}\) と \(v_{i}\) の leader が同じ場合、 merge すると閉路になる。

コード例1

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int main() {
  int N, M;
  cin >> N >> M;

  dsu uf(N);

  vector<int> hasLoop;
  rep(i, M) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    if(uf.leader(u) == uf.leader(v)) {
      hasLoop.push_back(u);
    }
    uf.merge(u, v);
  }

  int n = hasLoop.size();
  set<int> hasLoopRoot;
  rep(i, n) {
    int h = hasLoop[i];
    hasLoopRoot.insert(uf.leader(h));
  }

  int ans = uf.groups().size();
  cout << ans - hasLoopRoot.size() << endl;
  return 0;
}

解法2

1. DFS を使った閉路判定。
2. 各頂点について訪れたことがあるか否かを確認する変数を用意しておく。
3. DFS ですでにおとづれたことがある頂点に再度訪れた場合、閉路があることになる。

コード例2

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int N, M;
vector<vector<int>> graph;
vector<bool> visited;
bool hasLoop;

void dfs(int current, int prev) {
  if(visited[current] == true) {
    hasLoop = true;
    return;
  }
  visited[current] = true;

  rep(i, int(graph[current].size())) {
    int next = graph[current][i];
    if(next != prev) {
      dfs(next, current);
    }
  }
}

int main() {
  cin >> N >> M;

  graph.resize(N);
  visited.resize(N);
  rep(i, M) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  int ans = 0;
  rep(i, N) {
    hasLoop = false;
    dfs(i, i);
    if(!hasLoop) {
      ans++;
    }
  }

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