graph/degree_sequence.hpp

• View this file on GitHub
• Last update: 2026-02-12 20:42:31+09:00
• Include: #include "graph/degree_sequence.hpp"
• Link: https://codeforces.com/contest/134/problem/C

Depends on

• ds/csr.hpp

Code

#include "ds/csr.hpp"

// O(N). 単純グラフの存在判定. Erdos-Gallai の定理.
bool check_degree_sequence(vc<int> deg) {
  int N = len(deg);
  if (N == 0) return true;
  ll sm = 0;
  vc<int> freq(N, 0);
  FOR(i, N) {
    int d = deg[i];
    if (!(0 <= d && d < N)) return false;
    freq[d]++, sm += d;
  }
  if (sm & 1) return false;
  int p = 0;
  FOR_R(x, N) FOR(freq[x]) deg[p++] = x;

  vi S = cumsum<ll>(deg);
  ll m = 0;  // # of d_i s.t. d_i>=k
  FOR_R(k, N + 1) {
    while (m < N && deg[m] >= k) ++m;
    ll lhs = S[k];
    ll rhs = k * (k - 1);
    if (m < k) {
      rhs += S[N] - S[k];
    } else {
      rhs += (m - k) * k;
      rhs += S[N] - S[m];
    }
    if (lhs > rhs) return false;
  }
  return true;
}

// O(N+M) time
// https://codeforces.com/contest/134/problem/C
pair<bool, vc<pair<int, int>>> construct_from_degree_sequence(vc<int> deg) {
  if (!check_degree_sequence(deg)) return {false, {}};
  int N = len(deg);
  CSR<int> csr(N);
  FOR(v, N) { csr.add(deg[v], v); }
  csr.build();
  vc<int> cnt(N), D(N), V(N);
  int p = 0;
  FOR(x, N) for (auto& v : csr[x]) cnt[x]++, D[p] = x, V[p] = v, ++p;
  assert(p == N);

  vc<pair<int, int>> ANS;
  vc<pair<int, int>> tmp;
  FOR_R(idx, N) {
    int v = V[idx], n = D[idx];
    cnt[D[idx]] -= 1, D[idx] = 0;
    int p = idx;  // [p,n) used
    while (n > 0) {
      int d = D[p - 1];
      int l = p - cnt[d];
      int m = min(n, cnt[d]);
      for (int i = l; i < l + m; ++i) {
        ANS.eb(V[i], v), D[i]--;
      }
      tmp.eb(d, m);
      n -= m, p = l;
    }
    for (auto& [d, m] : tmp) cnt[d] -= m, cnt[d - 1] += m;
    tmp.clear();
  }
  return {true, ANS};
}

#line 1 "ds/csr.hpp"

template <typename T>
struct CSR {
  int n;
  bool prepared;
  vc<int> ptr;
  vc<int> I;
  vc<T> dat;

  CSR(int n = 0) : n(n), prepared(false) {}
  void add(int i, const T& x) {
    assert(0 <= i && i < n && !prepared);
    I.eb(i), dat.eb(x);
  }

  void build() {
    assert(!prepared);
    prepared = 1;
    ptr.assign(n + 1, 0);
    for (auto& i : I) ptr[1 + i]++;
    FOR(i, len(ptr) - 1) ptr[i + 1] += ptr[i];
    vc<T> tmp(len(dat));
    FOR(k, len(dat)) {
      int i = I[k];
      tmp[ptr[i]++] = dat[k];
    }
    swap(dat, tmp);
    ptr.pop_back();
    ptr.insert(ptr.begin(), 0);
    I.clear(), I.shrink_to_fit();
  }

  struct range {
    T *first, *last;
    T* begin() const { return first; }
    T* end() const { return last; }
  };

  range operator[](int i) {
    assert(prepared);
    return range{dat.data() + ptr[i], dat.data() + ptr[i + 1]};
  }
};
#line 2 "graph/degree_sequence.hpp"

// O(N). 単純グラフの存在判定. Erdos-Gallai の定理.
bool check_degree_sequence(vc<int> deg) {
  int N = len(deg);
  if (N == 0) return true;
  ll sm = 0;
  vc<int> freq(N, 0);
  FOR(i, N) {
    int d = deg[i];
    if (!(0 <= d && d < N)) return false;
    freq[d]++, sm += d;
  }
  if (sm & 1) return false;
  int p = 0;
  FOR_R(x, N) FOR(freq[x]) deg[p++] = x;

  vi S = cumsum<ll>(deg);
  ll m = 0;  // # of d_i s.t. d_i>=k
  FOR_R(k, N + 1) {
    while (m < N && deg[m] >= k) ++m;
    ll lhs = S[k];
    ll rhs = k * (k - 1);
    if (m < k) {
      rhs += S[N] - S[k];
    } else {
      rhs += (m - k) * k;
      rhs += S[N] - S[m];
    }
    if (lhs > rhs) return false;
  }
  return true;
}

// O(N+M) time
// https://codeforces.com/contest/134/problem/C
pair<bool, vc<pair<int, int>>> construct_from_degree_sequence(vc<int> deg) {
  if (!check_degree_sequence(deg)) return {false, {}};
  int N = len(deg);
  CSR<int> csr(N);
  FOR(v, N) { csr.add(deg[v], v); }
  csr.build();
  vc<int> cnt(N), D(N), V(N);
  int p = 0;
  FOR(x, N) for (auto& v : csr[x]) cnt[x]++, D[p] = x, V[p] = v, ++p;
  assert(p == N);

  vc<pair<int, int>> ANS;
  vc<pair<int, int>> tmp;
  FOR_R(idx, N) {
    int v = V[idx], n = D[idx];
    cnt[D[idx]] -= 1, D[idx] = 0;
    int p = idx;  // [p,n) used
    while (n > 0) {
      int d = D[p - 1];
      int l = p - cnt[d];
      int m = min(n, cnt[d]);
      for (int i = l; i < l + m; ++i) {
        ANS.eb(V[i], v), D[i]--;
      }
      tmp.eb(d, m);
      n -= m, p = l;
    }
    for (auto& [d, m] : tmp) cnt[d] -= m, cnt[d - 1] += m;
    tmp.clear();
  }
  return {true, ANS};
}

Back to top page