ARC 106 | B - Values

問題

https://atcoder.jp/contests/arc106/tasks/arc106_b

考えたこと

以下のようなグラフが複数あり、複数の操作をすることにより黒から赤の値にできるかという問題である。

解説にもある通り、あるグラフにおいて $\sum_{i} a_i = \sum_{i} b_i$ ならばそのグラフは条件を満たせる。以下のようにグラフが連結しているなら任意の2つの頂点$a_i$, $a_j$について、$a_i$を+1、$a_j$を-1することが可能であるからである。

グラフが連結しているかどうかはUnion-Findを使えばいい。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }

  dsu uf = dsu(n);
  for (int i = 0; i < m; i++) {
    int c, d;
    cin >> c >> d;
    // 0-indexed
    c--;
    d--;
    uf.merge(c, d);
  }

  for (auto group : uf.groups()) {
    ll av = 0;
    ll bv = 0;
    for (auto i : group) {
      av += a[i];
      bv += b[i];
    }
    if (av != bv) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

参考

• 解説: https://atcoder.jp/contests/arc106/editorial/247