bnu 34981 A Matrix(構造)

題目鏈接：bnu 34981 A Matrix

題目大意：假定有一序列，按照題目中給定的算法構造出一張二維表，現在題目給定一張二維表，要求求出序列，要求序列的倒置的字典序最大。

解題思路：構造，對於每一層來說，一定是遞增的，根據算法可以得出；並且一個數被換到下一行，一定是因為有序列後面有小於自己的數，所以每一層從最後一個數開始匹配，找到上一層中比自己小的最大數字，假定是該數導致當前數被換到下一行，注意一個數只能讓一個數被換到下一行。所以有幾種是找不到對應序列，要輸出-1.

• 一行中的數不是遞增的。
• 當前行的數不能一一對應上一行的數
  

  #include 
  #include 
  #include 
  #include 
  
  using namespace std;
  const int N = 1e5+5;
  
  bool flag;
  int n, m, c, mv, f[N], r[N], ans[N];
  vector g[N];
  
  int getfar(int x) {
      return x == f[x] ? x : f[x] = getfar(f[x]);
  }
  
  void init () {
      scanf("%d%d", &n, &m);
  
      flag = false;
      for (int i = 0; i <= n; i++)
          r[i] = f[i] = i;
      for (int i = 0; i < m; i++)
          g[i].clear();
  
      int t;
      for (int i = 0; i < m; i++) {
          scanf("%d", &t);
          int a, pre = 0;
  
          for (int j = 0; j < t; j++) {
              scanf("%d", &a);
              g[i].push_back(a);
              if (a < pre)
                  flag = true;
              pre = a;
          }
      }
  }
  
  bool insert (int x, int d) {
  
      for (int j = mv-1; j >= 0; j--) {
          if (g[d][j] < x) {
              int p = getfar(g[d][j]);
              f[p] = x;
              r[p] = x;
              mv = j;
              return true;
          }
      }
      return false;
  }
  
  void put(int x) {
      ans[c--] = x;
      if (r[x] != x)
          put(r[x]);
  }
  
  void solve () {
  
      for (int i = m-1; i; i--) {
          int t = g[i].size();
  
          mv = g[i-1].size();
  
          for (int j = t-1; j >= 0; j--)
              if (!insert(g[i][j], i-1)) {
                  flag = true;
                  return;
              }
      }
  
      c = n;
      int t = g[0].size();
      for (int i = t-1; i >= 0; i--)
          put(g[0][i]);
  }
  
  int main () {
      int cas; 
      scanf("%d", &cas);
      for (int i = 1; i <= cas; i++) {
          init ();
  
          printf("Case #%d: ", i);
          solve();
  
          if (flag) {
              printf("No solution\n");
          } else {
              for (int j = 1; j < n; j++)
                  printf("%d ", ans[j]);
              printf("%d\n", ans[n]);
          }
      }
      return 0;
  }