想定解の解説と同様に、強連結成分分解(SCC) をしてDAG上の問題に帰着します。 時間計算量 \(O(NM)\) で各 \((i, j) ~ (1 \le i < j \le N)\) に対し \(i\) から \(j\) へのパスがあるか調べられます。\(i\) から \(j\) へのパスがあれば、\(i\) から \(j\) への辺を張ることを繰り返します。

辺を張り終えたグラフの 最小パス被覆 において、 頂点 \(i, j\) が最小パス被覆によって選ばれる辺で繋がっているなら、頂点 \(i, j\) を同じ色で塗ります。そうすると、\(\max\{c_1, \cdots, c_N\}\) が最小になります。

辺を張り終えたグラフは DAG です。DAG の最小パス被覆問題は二部グラフの最大マッチング問題に帰着し、最大流によって多項式時間で解くことができます。Dinic法を使うと、時間計算量は \(O(N^{2.5})\)、空間計算量は \(O(N^2)\) です。

C++ などの処理の速い言語だと時間計算量は大丈夫ですが、空間計算量が重くてメモリ制限に引っかかります。そこで、ネットワークフローの容量がすべて \(1\) であることに注目し、たとえば C++ で vector<bool> を用いて各辺の流量を管理する密グラフ用のDinic法（詳しくは実装例を参照）を実装すると、bool型の配列の使用メモリが軽いことを利用してメモリ制限を突破することができます。

結局、この解法の時間計算量は \(O(NM + N^{2.5})\)、空間計算量は \(O(N^2)\) です。

実装例(C++)