データ構造/素集合データ構造/重みつき union-find
(test/data_structure/union-find/weighted_union-find.test.cpp)

• View this file on GitHub
• Last update: 2023-02-26 01:10:01+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B

Depends on

• 重みつき union-find (include/emthrm/data_structure/union-find/weighted_union-find.hpp)

Code

/*
 * @title データ構造/素集合データ構造/重みつき union-find
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B
 */

#include <iostream>

#include "emthrm/data_structure/union-find/weighted_union-find.hpp"

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::WeightedUnionFind<int> union_find(n);
  while (q--) {
    int query;
    std::cin >> query;
    if (query == 0) {
      int x, y, z;
      std::cin >> x >> y >> z;
      union_find.unite(x, y, z);
    } else if (query == 1) {
      int x, y;
      std::cin >> x >> y;
      if (union_find.is_same(x, y)) {
        std::cout << union_find.diff(x, y) << '\n';
      } else {
        std::cout << "?\n";
      }
    }
  }
  return 0;
}

#line 1 "test/data_structure/union-find/weighted_union-find.test.cpp"
/*
 * @title データ構造/素集合データ構造/重みつき union-find
 *
 * verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B
 */

#include <iostream>

#line 1 "include/emthrm/data_structure/union-find/weighted_union-find.hpp"



#include <utility>
#include <vector>

namespace emthrm {

template <typename Abelian>
struct WeightedUnionFind {
  explicit WeightedUnionFind(const int n, const Abelian ID = 0)
      : ID(ID), parent(n, -1), data(n, ID) {}

  int root(const int ver) {
    if (parent[ver] < 0) return ver;
    const int r = root(parent[ver]);
    data[ver] += data[parent[ver]];
    return parent[ver] = r;
  }

  bool unite(int u, int v, Abelian wt) {
    wt += weight(u);
    wt -= weight(v);
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (parent[u] > parent[v]) {
      std::swap(u, v);
      wt = -wt;
    }
    parent[u] += parent[v];
    parent[v] = u;
    data[v] = wt;
    return true;
  }

  bool is_same(const int u, const int v) { return root(u) == root(v); }

  int size(const int ver) { return -parent[root(ver)]; }

  Abelian diff(const int u, const int v) { return weight(v) - weight(u); }

 private:
  const Abelian ID;
  std::vector<int> parent;
  std::vector<Abelian> data;

  Abelian weight(const int ver) {
    root(ver);
    return data[ver];
  }
};

}  // namespace emthrm


#line 10 "test/data_structure/union-find/weighted_union-find.test.cpp"

int main() {
  int n, q;
  std::cin >> n >> q;
  emthrm::WeightedUnionFind<int> union_find(n);
  while (q--) {
    int query;
    std::cin >> query;
    if (query == 0) {
      int x, y, z;
      std::cin >> x >> y >> z;
      union_find.unite(x, y, z);
    } else if (query == 1) {
      int x, y;
      std::cin >> x >> y;
      if (union_find.is_same(x, y)) {
        std::cout << union_find.diff(x, y) << '\n';
      } else {
        std::cout << "?\n";
      }
    }
  }
  return 0;
}

Back to top page