Submission #66813375

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (auto& [l, r]: a) cin >> l >> r;
    vector<vector<int>> G(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i == j) continue;
        if (a[i].first <= a[j].first && a[i].second >= a[j].second) {
          G[i].push_back(j);
        }
      }
    }

    for (int i = 0; i < n; i++) sort(G[i].begin(), G[i].end());
    
    int t = 1;
    vector<int> ans(n), used(n);
    auto dfs = [&] (auto&& self, int v) -> void {
      if (used[v]) return;
      for (int u: G[v]) {
        if (!used[u]) {
          self(self, u);
        }
      }
      used[v] = 1;
      ans[v] = t++;
    };

    for (int i = 0; i < n; i++) dfs(dfs, i);
    for (auto& x: ans) cout << x << ' ';
    cout << '\n';
  }
}

Submission Info

Judge Result