AtCoder Beginner Contest 126 E - 1 or 2

考えたこと：

・Zは定数なので、ほとんど関係ない。（ＭＯＤ　２をとって終わり）

・Ax1+Ay1のＭＯＤ　２が解っているとき、、片方の値が判明すればもう片方も判明する。（０か１しかないので）

・ＡがわかればＢもわかるという関係を連結と呼ぶならば、２つの場合のみならず、３つ４つの連結な関係も考えられるのではないか？

ー＞実際、考えられる。

この連結な関係はグラフで表すことが出来そう。

ー＞UnionFindTreeで表せばもっと簡潔に表せそう。

実装：

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct UnionFind {
  vector<int> data;

  UnionFind(int sz) {
    data.assign(sz, -1);
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return (false);
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k) {
    if (data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k) {
    return (-data[find(k)]);
  }
};

int N, M;
UnionFind uf(101010);

signed main() {
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    x--, y--;
    uf.unite(x, y);
  }

  vector<int> v;
  for (int i = 0; i < N; i++) {
    v.push_back(uf.find(i));
  }

  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());

  cout << v.size() << endl;

  return 0;
}

細かい実装の部分を付け足すと、具体的な答えはＵＦ上の連結部分の個数、すなわちＵＦの頂点の親の個数となる。

よって、vectorに親を入れていき最後にuniqueで重複部分を除いてvectorのサイズを答えている。