test/atcoder/abc177_d.test.cpp

View this file on GitHub
Last update: 2023-07-30 00:54:52+09:00
Problem: https://atcoder.jp/contests/abc177/tasks/abc177_d

Depends on

Code

// verification-helper: PROBLEM https://atcoder.jp/contests/abc177/tasks/abc177_d

#include "src/cpp-template/header/change-max.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/data-structure/disjoint-set-union.hpp"

#include <cassert>
#include <iostream>

namespace luz {

  void main_() {
    usize n, m;
    std::cin >> n >> m;

    DisjointSetUnion dsu(n);
    for ([[maybe_unused]] usize _: rep(0, m)) {
      usize u, v;
      std::cin >> u >> v;
      dsu.merge(u - 1, v - 1);
    }

    usize ans1 = 0, ans2 = 0;
    {
      for (usize v: rep(0, n)) {
        chmax(ans1, dsu.group_size(v));
      }
    }
    {
      auto groups = dsu.groups();
      for (const auto &group: groups) {
        chmax(ans2, group.size());
      }
    }

    assert(ans1 == ans2);

    usize ans = ans1;
    std::cout << ans << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}

#line 1 "test/atcoder/abc177_d.test.cpp"
// verification-helper: PROBLEM https://atcoder.jp/contests/abc177/tasks/abc177_d

#line 2 "src/cpp-template/header/change-max.hpp"

namespace luz {

  template < typename T1, typename T2 >
  inline bool chmax(T1 &a, T2 b) {
    return a < b and (a = b, true);
  }

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 2 "src/data-structure/disjoint-set-union.hpp"

#line 5 "src/data-structure/disjoint-set-union.hpp"

#line 7 "src/data-structure/disjoint-set-union.hpp"
#include <cassert>
#include <vector>

namespace luz {

  class DisjointSetUnion {
    usize n;

    // vals[v] :=
    //   if v is root node: -1 * component size
    //   otherwise: parent node
    std::vector< isize > vals;

    void bound_check(usize v) const {
      assert(v < n);
    }

    usize impl_leader(usize v) {
      if (vals[v] < 0) return v;
      return vals[v] = leader(vals[v]);
    }

   public:
    DisjointSetUnion() = default;
    explicit DisjointSetUnion(usize n): n(n), vals(n, -1) {}

    usize size() const {
      return n;
    }

    usize leader(usize v) {
      bound_check(v);
      return impl_leader(v);
    }

    bool same(usize u, usize v) {
      bound_check(u), bound_check(v);
      return impl_leader(u) == impl_leader(v);
    }

    usize merge(usize u, usize v) {
      bound_check(u);
      bound_check(v);

      isize x = impl_leader(u);
      isize y = impl_leader(v);
      if (x == y) return x;
      if (-vals[x] < -vals[y]) std::swap(x, y);
      vals[x] += vals[y];
      vals[y] = x;
      return x;
    }

    usize group_size(usize v) {
      bound_check(v);
      return -vals[impl_leader(v)];
    }

    std::vector< std::vector< usize > > groups() {
      std::vector< std::vector< usize > > result(n);

      std::vector< usize > leaders(n), g_sizes(n);
      for (usize v: rep(0, n)) {
        leaders[v] = impl_leader(v);
        g_sizes[leaders[v]]++;
      }
      for (usize v: rep(0, n)) {
        result[v].reserve(g_sizes[v]);
      }
      for (usize v: rep(0, n)) {
        result[leaders[v]].emplace_back(v);
      }

      auto empty_check = [](const std::vector< usize > &vs) {
        return vs.empty();
      };
      result.erase(
          std::remove_if(result.begin(), result.end(), empty_check),
          result.end());

      return result;
    }
  };

} // namespace luz
#line 7 "test/atcoder/abc177_d.test.cpp"

#line 9 "test/atcoder/abc177_d.test.cpp"
#include <iostream>

namespace luz {

  void main_() {
    usize n, m;
    std::cin >> n >> m;

    DisjointSetUnion dsu(n);
    for ([[maybe_unused]] usize _: rep(0, m)) {
      usize u, v;
      std::cin >> u >> v;
      dsu.merge(u - 1, v - 1);
    }

    usize ans1 = 0, ans2 = 0;
    {
      for (usize v: rep(0, n)) {
        chmax(ans1, dsu.group_size(v));
      }
    }
    {
      auto groups = dsu.groups();
      for (const auto &group: groups) {
        chmax(ans2, group.size());
      }
    }

    assert(ans1 == ans2);

    usize ans = ans1;
    std::cout << ans << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}