Codeforces/1829/f.cpp

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

template <typename T, typename U>
std::ostream &operator<<(std::ostream &s, std::pair<T, U> const &p) {
  return s << p.first << " " << p.second;
}

namespace helpers {

using namespace std;

namespace math {

long pow(long base, long exp) {
  if (exp == 0) return 1;
  long half = pow(base, exp / 2);
  if (exp % 2 == 0) return half * half;
  return half * half * base;
}

}  // namespace math

namespace input {

template <typename T>
std::vector<T> load_vector(std::size_t size) {
  std::vector<T> result{};

  for (auto i = 0u; i < size; ++i) {
    T x;
    std::cin >> x;
    result.push_back(std::move(x));
  }

  return result;
}

}  // namespace input

namespace output {

template <typename T>
inline void answer(const T &ans) {
  cout << ans << "\n";
}

inline void yes() { cout << "YES\n"; }
inline void no() { cout << "NO\n"; }

inline void yesno(bool ans) {
  if (ans) {
    yes();
  } else {
    no();
  }
}

}  // namespace output

using namespace math;
using namespace input;
using namespace output;

#define LOOP(n) for (auto i = 0; i < n; ++i)

}  // namespace helpers

// for ‹N› test cases, uncomment for single test case
// #define SINGLE

namespace solution {

using namespace std;
using namespace helpers;

struct vertex {
  set<int> neighbours;
};

pair<int, int> determine_snowflake(const map<int, vertex> &vertices) {
  map<int, int> counts;

  int leaf_parent = -1;
  for (const auto &mapping : vertices) {
    auto v = mapping.second;

    if (v.neighbours.size() == 1) {
      leaf_parent = *v.neighbours.begin();
      continue;
    }

    counts[v.neighbours.size()]++;
  }

  int y = vertices.at(leaf_parent).neighbours.size() - 1;

  // V = 1 + x + x * y
  // V - 1 = x + x * y
  // V - 1 = x * (1 + y)
  // x = (V - 1) / (y + 1)
  int x = (vertices.size() - 1) / (y + 1);

  return {x, y};
}

void solve() {
  int V, E;
  cin >> V >> E;

  map<int, vertex> vertices;
  LOOP(E) {
    int u, v;
    cin >> u >> v;

    vertices[u].neighbours.insert(v);
    vertices[v].neighbours.insert(u);
  }

  answer(determine_snowflake(vertices));
}

}  // namespace solution

using namespace solution;

#ifdef TEST

#include "../.common/cpp/catch_amalgamated.hpp"

static map<int, vertex> edges_to_graph(vector<pair<int, int>> edges) {
  map<int, vertex> vertices;

  for (auto [u, v] : edges) {
    vertices[u].neighbours.insert(v);
    vertices[v].neighbours.insert(u);
  }

  return vertices;
}

TEST_CASE("examples") {
  CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
            {21, 20}, {21, 20}, {5, 20}, {13, 20}, {1, 3},  {11, 3},
            {10, 3},  {4, 8},   {19, 8}, {14, 8},  {9, 7},  {12, 7},
            {17, 7},  {18, 6},  {16, 6}, {2, 6},   {6, 15}, {7, 15},
            {8, 15},  {20, 15}, {3, 15}})) == pair{5, 3});
  CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
            {7, 6}, {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}})) ==
        pair{2, 2});
  CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
            {9, 8},
            {9, 3},
            {3, 6},
            {6, 2},
            {2, 1},
            {5, 2},
            {2, 7},
            {4, 3},
            {3, 8},
        })) == pair{2, 3});
  CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
            {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}})) == pair{2, 2});
  CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
            {1, 2},  {1, 3},  {1, 4},  {1, 5},  {1, 6},  {2, 21}, {2, 22},
            {2, 23}, {2, 24}, {3, 31}, {3, 32}, {3, 33}, {3, 34}, {4, 41},
            {4, 42}, {4, 43}, {4, 44}, {5, 51}, {5, 52}, {5, 53}, {5, 54},
            {6, 61}, {6, 62}, {6, 63}, {6, 64},
        })) == pair{5, 4});
}

#else

int main(void) {

#ifdef SINGLE

  solution::solve();

#else

  // for multiple test cases
  int N;
  std::cin >> N >> std::ws;

  for (auto i = 0; i < N; ++i) {
    solution::solve();
  }

#endif

  return 0;
}

#endif