🕌

ABC223 D - Restricted Permutation C++解答例

2021/10/19に公開

C++

AtCoder Beginner Contest 233 D - Restricted PermutationをC++で解きます。

問題

問題文をAtCoderのページより引用します。

問題文

$(1, 2, \ldots, N)$ を並び替えて得られる数列 $P$ であって以下の条件を満たすもののうち、辞書順で最小のものを求めてください。

$i = 1, \ldots, M$ に対し、 $P$ において $A_{i}$ は $B_{i}$ よりも先に現れる。

ただし、そのような $P$ が存在しない場合は-1と出力してください。

制約

$2 \leq N \leq 2 \times 10^{5}$

$1 \leq M \leq 2 \times 10^{5}$

$1 \leq A_{i}, B_{i} \leq N$

$A_{i} \neq B_{i}$

入力はすべて整数である。

解答例

考え方：工夫したトポロジカルソートを使う

「 $M$ 個の順序制約の中で $N$ 個の数字を並び替える」と聞くと、なんとなくトポロジカルソートみを感じます。
実際これは工夫したトポロジカルソートによって解くことができます。ただし、再帰関数の帰りがけ順によって求めるトポロジカルソートではなく、幅優先探索ライクなトポロジカルソートを応用する必要があります。^[1]

問題で与えられる $M$ 個の制約を観察してみます。「順列 $P$ において $A_{i}$ は $B_{i}$ よりも先に現れる」を言い換えると、「 $B_{i}$ は $A_{i}$ が現れるまで順列に現れることはできない」となります。
更に言い換えると「 $A_{i}$ が出てきた後は $B_{i}$ が現れても良い」とも言えます。
また、それまでにかかっていた制約が全て外れたノード、あるいは制約が最初から無いノードは、任意のタイミングで順列 $P$ に現れても良いことが分かります。

これを別の言い方で表現すれば、あるノードの入次数^[2]が0の場合はそのノードを自由なタイミングで順列 $P$ へ挿入でき、入次数が1以上の場合は制約が解決するまで順列 $P$ には挿入できない(制約が解決した=入次数が0になったとき初めて順列 $P$ に挿入できる)ということになります。

長々と書いてしまいましたが、結局のところ幅優先探索ライクにトポロジカルソートを行うアルゴリズムは、以下のような流れで表されます。

グラフを構築し、同時に各ノードの入次数をメモしておく。
ソートした結果を格納する配列 $S$ を用意する。
入次数が0のノードを1つ取り出す。これをノード $v$ とおく。
配列 $S$ に $v$ を挿入する。
$v$ から出ているエッジをグラフから取り除く。
入次数が0のノードがなくなるまで3.から5.を繰り返す。
繰り返しが終了した時点で、配列 $S$ のサイズがノード数 $N$ と一致しているならば、そのグラフはトポロジカルソート可能であり、その結果は $S$ である。そうでなければそのグラフはトポロジカルソート不可である。

通常トポロジカルソートを実装する場合、上記のアルゴリズムの3.におけるノードの取り出し方をキューで管理します。
しかし、今回の問題では、トポロジカルソートした結果のうち、辞書順で最小のものを得たいと考えます。
そこで、この部分で使うデータ構造をキューではなく優先度付きキューで管理します。

入次数が0のノードが複数あるとき、値が小さいノードから順に取り出せば、取り出した結果は辞書順で最小のものとなります。

実装例

実際にコードを見た方が早いと思うのでコード全体を示します。

d.cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <queue>
 
int main() {
  int64_t N, M;
  std::cin >> N >> M;
  std::vector<std::vector<int64_t>> graph(N);
  // 各ノードの入次数をメモしておくための配列
  std::vector<int64_t> indegree(N, 0);
  for (int64_t i = 0; i < M ; i++) {
    int64_t a, b;
    std::cin >> a >> b;
    // 0-indexedでグラフを構築する
    graph.at(a - 1).push_back(b - 1);
    // 入次数を記録していく
    indegree.at(b - 1)++;
  }
 
  // 値が小さいものの優先度を高くする 
  std::priority_queue<int64_t, std::vector<int64_t>, std::greater<int64_t>> heap;
  // グラフが構築された時点で入次数が0のノードを優先度付きキューに追加する
  for (int64_t i = 0; i < N; i++) {
    if (indegree.at(i) == 0) {
      heap.push(i);
    }
  }
 
  // トポロジカルソートした結果を格納する配列
  std::vector<int64_t> answer;
  // 入次数が0のノードが無くなるまで繰り返す
  while (!heap.empty()) {
    // 優先度付きキューからノードを1つ取り出し、そのノードを削除する
    int64_t node = heap.top();
    heap.pop();
 
    // 取り出したノードを答えに追加する
    answer.push_back(node);
    for (int64_t next_node : graph.at(node)) {
      // 取り出したノードから伸びているエッジをグラフから取り除く
      indegree.at(next_node)--;
      // エッジを削除したことによりその先のノードの入次数が0になったら、それも優先度付きキューに追加する
      if (indegree.at(next_node) == 0) {
        heap.push(next_node);
      }
    }
  }
 
  // 答えの配列のサイズがNに等しかったらトポロジカルソート可能である
  if (static_cast<int64_t>(answer.size()) == N) {
    for (int64_t i = 0; i < N; i++) {
      if (i) std::cout << " ";
      std::cout << answer.at(i) + 1; // 0-indexedでグラフを構築したので答えを出力するときは+1しておく
    }
    std::cout << std::endl;
  } else {
    std::cout << -1 << std::endl;
  }
 
  return 0;
}

実際に提出したコードはこちら。

参考文献

脚注

私は再帰関数を使った実装しか知らなかったのでコンテスト中に解くことができませんでした。 ↩︎
そのノードに入ってくるエッジの数のこと。 ↩︎

問題

問題文

制約

解答例

考え方：工夫したトポロジカルソートを使う

実装例

参考文献

Discussion