提出 #7314254

---

ソースコード 拡げる

#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

map<PLL, vector<PLL>> nexts; // edges[v]: {u1, u2, ..}
map<PLL, ll> prevs;
vector<ll> a[2000];

PLL ver(ll i, ll j) {
  if (i > j)
    swap(i, j);
  return PLL(i, j);
}

signed main() {
  ll N;
  cin >> N;
  rep(i,N) {
    rep(j,N-1) {
      ll x;
      cin >> x;
      x--;
      a[i].push_back(x);
    }
  }
  rep(i,N) {
    rep(j,N-2) {
      auto cur = ver(i, a[i][j]);
      auto nex = ver(i, a[i][j+1]);
      nexts[cur].push_back(nex);
      prevs[nex]++;
      // printf("cur: (%d, %d) nex: (%d, %d)\n", cur.first, cur.second, nex.first, nex.second);
    }
  }

  // deleted candinates
  vector<PLL> can;
  rep(i,N) rep(j,i) {
    auto v = ver(i,j);
    if (prevs[v] == 0){
      can.push_back(v);
    }
  }
  //for (auto e : can) {
  //  printf("(%d, %d)\n", e.first, e.second);
  //}

  ll ans = 0;
  ll done = 0;
  while (done < N*(N-1)/2) {
    if (can.size() == 0) {
      cout << -1 << endl;
      return 0;
    }
    vector<PLL> t;
    for (auto v : can) {
      done++;
      for (auto u: nexts[v]) {
        prevs[u]--;
        if (prevs[u] == 0) {
          t.push_back(u);
        }
      }
    }
    can = t;
    ans++;
  }

  cout << ans << endl;
  return 0;
}

提出情報

ジャッジ結果