準備

まず、頂点 \(i\) と頂点 \(j\) が強連結、すなわち, 頂点 \(i\) から頂点 \(j\) へのパスと頂点 \(j\) から頂点 \(i\) へのパスがともに存在するとしたら、それらの頂点は同じ色で塗ることができます。よって、塗る色の数を最小にするとき、同じ強連結成分に属する頂点はすべて同じ色で塗るのが最適です。

したがって、強連結成分分解(SCC)により強連結成分を縮約することでこの問題は DAG 上の同じ問題に帰着できます。以下では、グラフが DAG であると仮定し、頂点番号が小さい順にトポロジカルソートされているとします。

整数のペアからなる集合 \(S \subset \mathbb{Z} \times \mathbb{Z}\) であって、次の条件1.～3.を満たすものを良い集合ということにします。

1. 任意の \((i, j) \in S\) について、\(i, j\) は \(1 \le i < j \le N\) を満たす整数である。
2. 頂点 \(i\) から頂点 \(j\) へのパスが存在する。
3. \((i, j), (i, k) \in S\) ならば \(j = k\) である。また、\((j, i), (k, i) \in S\) ならば \(j = k\) である。

\(i < j\) であるとき、頂点 \(i\) から頂点 \(j\) へのパスが存在するならば、\(i, j\) は同じ色で塗ることができます。よって、\(S\) を良い集合とすると、\((i, j) \in S\) について \(i, j\) は同じ色に塗ることができます。

逆に、色を塗り終えたグラフにおいて、色 \(r\) で塗られた頂点番号を小さい順に \(v_1, \cdots, v_k\) (\(k\) は非負整数) とし、集合 \(S_r\) を \(S_r = (v_1, v_2), \cdots, (v_{k-1}, v_k)\) （ただし、\(k=0,1\) のときは \(S_r\) は空）とすると、集合 \(S = S_1 \cup \cdots \cup S_N\) は良い集合です。

よって、グラフの頂点に色を塗ることは良い集合 \(S\) を定めることと同一視できます。また、ある \(2\) つの頂点を同じ色で塗ったとき、全体で色の数は \(1\) だけ減ります。したがって、良い集合 \(S\) の要素数だけ使う必要のある色が減り、適切に色を塗れば \(\max\{c_1, \cdots, c_N\} = N - |S|\) となります。以上から、良い集合 \(S\) のなかで要素数が最大のものを作れば \(\max\{c_1, \cdots, c_N\}\) を最小化できます。

想定解

以下のネットワークを考えます。

• 以下の頂点を用意する。
  • \(\text{src}, \text{dst}\)
  • \(U_1, \cdots, U_N\)
  • \(V_1, \cdots, V_N\)
• \(\text{src}\) からすべての \(V_i\) へ容量 \(1\) の辺を張る。
• すべての \(U_i\) から \(\text{dst}\) へ容量 \(1\) の辺を張る。
• 各辺 \(i = 1, \cdots, M\) に対し、\(V_{A_i}\) から \(U_{B_i}\) へ容量 \(\infty\) の辺を張る。
• すべての \(U_i\) から \(V_i\) へ容量 \(\infty\) の辺を張る。

（流量は \(N\) 以下なので、実際は容量 \(\infty\) は \(N\) としてよいです）

このとき \(\text{src}\) から \(\text{dst}\) へのフローは \((i, j)\) (\(1 \le i < j \le N\)) の組の集合を定めていると解釈できます。ある解釈によって \(\text{src} \to V_i \to \cdots \to U_j \to \text{dst}\) に流れている組 \((i, j)\) の集合を \(S\) とすると、\(S\) は良い集合になります。また、フローの流量を \(F\) とすると、\(F=|S|\) が成り立ちます。ただし、フローから良い集合 \(S\) への対応は一意ではありません。

逆に、良い集合 \(S\) は \((i, j) \in S\) すべてについて \(\text{src} \to V_i \to \cdots \to U_j \to \text{dst}\) に流量 \(1\) 流すと、\(\text{src}\) から \(\text{dst}\) へのフローになります。

よって、良い集合 \(S\) と、このネットワーク上のフローは同一視できます。したがって、\(|S|\) が最大になるものを求めるためには、\(\text{src}\) から \(\text{dst}\) への最大流を求めればよいです。このネットワークの最大流量は \(N\)、辺の本数は最大で \(3N+M\) であるので、Ford-Fulkerson 法を使えば時間計算量 \(O(N(N+M))\)、空間計算量 \(O(N+M)\) で最大流を求められます。

最大流を流したあと、各フローの流量を見れば、時間計算量 \(O(N^2)\)、空間計算量 \(O(N)\) でグラフに色を塗ることができます。

最後に、強連結成分分解で縮約したグラフをもとに戻して出力すればよいです。全体で時間計算量は \(O(N(N+M))\)、空間計算量は \(O(N+M)\) です。

実装例(C++, Fold-Fulkerson 法)

実装例(C++, Dinic法: AtCoder Library)

実装例(Pypy3, Dinic法)

Pypy3の 実装例は ac-library-python のライブラリを使いました.