JOI2008 春合宿 sheet

問題ページ
http://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf

考えたこと

色iが色jの上に乗っていることをjからiへの有向辺が張られている状態と考えるとトポロジカルソートをすればよい。O(HWN)で辺を張ればよく、トポロジカルソートはO(N^2)でできるので計算量は問題ない。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int c[105][105], sx[1010], sy[1010], gx[1010], gy[1010];
//グラフの隣接リスト
VI g[100010];
//頂点の入次数を管理
int h[100010];
signed main(void)
{
  int hh, w, n;
  cin >> n >> w >> hh;
  REP(i, hh) REP(j, w) cin >> c[i][j];

  memset(sx, 0x3f, sizeof(sx));
  memset(sy, 0x3f, sizeof(sy));
  REP(i, hh) REP(j, w) {
    chmin(sx[c[i][j]], (int)j);
    chmin(sy[c[i][j]], (int)i);
    chmax(gx[c[i][j]], (int)j);
    chmax(gy[c[i][j]], (int)i);
  }

  REP(i, hh) REP(j, w) FOR(k, 1, n+1) {
    int co = c[i][j];
    if(co == 0 || co == k) continue;
    if(IN(sx[k], gx[k]+1, j) && IN(sy[k], gy[k]+1, i)) {
      // coがkの上に乗っている
      g[k].push_back(co);
      h[co]++;
    }
  }

  //入次数が0の頂点の集合
  stack<int> st;

  //入次数が0の頂点であればstに追加
  FOR(i, 1, n+1) if(h[i] == 0) st.push(i);

  //ソートされた後のグラフ
  VI ans;
  //stがなくなるまでループ
  while(st.size()) {
    //stの集合のから一つ取り出す
    int i = st.top(); st.pop();
    ans.push_back(i);
    for(auto& j: g[i]) {
      //隣接する頂点の入次数をマイナス1
      h[j]--;
      //これによって入次数が0になればstに追加
      if(h[j] == 0) st.push(j);
    }
  }

  //ansを順に出力
  REP(i, ans.size()) {
    cout << ans[i];
    if(i != ans.size()-1) cout << " ";
  }
  cout << endl;

  return 0;
}