AtCoder ABC139-E を有向グラフ初心者がC++で解く

ABC139 - E に挑戦します。

最初は、n日目に出場する選手のリストを作って探索しようと思いましたがうまくいかず、解説を読む。

https://img.atcoder.jp/abc139/editorial.pdf

「$N(N-1)/2$試合のそれぞれを頂点に見立て、（略）有向グラフを考えます。」「閉路検出と最大パス長の算出」と書いてあったのでまずは閉路検出とやらを勉強することにした。

挑戦前の能力 : キューとスタックで無向グラフのBFSとDFSができる

用語など

とりあえずこの記事の内容がつかめる程度の説明

• グラフ, 頂点, 辺 : 下の図のようなものがグラフ。丸で囲ったところが頂点、頂点をつないでいるのが辺。今回は辺が矢印になっている（向きを持っている）ので有向グラフ。

• 入次数 : それぞれの頂点において、矢印が「刺さっている」数。例えば頂点1は入次数0。頂点4は入次数2（出る矢印は数えない）。

• 閉路 : 要するにループ。先ほどのグラフに、$7 \rightarrow 2$ の辺をつけると $2 \rightarrow 5 \rightarrow 7 \rightarrow 2$ というふうに閉路が形成される。

• 有向非巡回グラフ DAG : 閉路がないグラフ（図のまま）を「有向非巡回グラフ (Directed Acyclic Graph = DAG)」という。

• トポロジカルソート : 辺が繋がったままグラフの頂点を1列に並べた時、矢印がすべて右向きになるようにソートすること。下図参照。なお、これには何通りか並べ方がある可能性もある。

+ グラフの入力 : 基本となる、グラフの入力方法。頂点の数 $N$ 、辺の数 $ M $ を入力し、続けて $ M $ 回、矢印の根元と行き先の頂点を入力。以下の例参照。

//入力例（上の図を示す）
7 8
1 2
1 4
2 3
2 5
4 3
5 7
6 4
6 5

トポロジカルソートとの出会い

トポロジカルソートのアルゴリズム（閉路のない有向グラフDAGのソート） | アルゴリズムロジック

この↑サイトによると、「トポロジカルソートができる」$\Leftrightarrow$「DAGである（閉路がない）」。

ということでトポロジカルソートを実装。先のサイトを参考に、BFS（幅優先探索）を用いて、AOJの以下のページに提出できるコードを書く。

トポロジカルソート - AOJ

• 入力について、AtCoderは（今まで示した例のように）頂点の番号が1始まりが多いが、AOJは0始まりであることに注意
• グラフの構造は二次元配列で示す。G[i]は頂点iから「行ける」頂点のリスト
• キューに入れるのは、入次数が0である頂点のリスト
• キューから取り出したら、ソート後のリストに追加し、繋がっている頂点の入次数をデクリメントする（取り出した頂点をグラフから削除することに相当）
• ソート後のリストに全要素が入っていれば閉路なし
• l_depthに各頂点の深さ（最大）を入れる（今は使わないけどあとで要る）

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

int N,M; //頂点と辺の数
vector<vector<int>> G; //グラフ
vector<int> h; //入次数
vector<int> l_depth; //最大経路長
vector<int> ans; //答えを格納

void input(){
  cin>>N>>M;
  G.resize(N);
  h.resize(N, 0); //入次数0初期化
  int f,t;
  for(int i=0; i<M; i++){
    cin>>f>>t;
    //f--; t--; //1始まりで辺の情報を入れるならデクリメントする
    G[f].push_back(t); //fからtに行ける
    h[t]++; //tの入次数を増やす
  }
}

void topoBFS(){   
  queue<int> unchecked;
  for(int i=0; i<N; i++){
    if(h[i]==0){
      unchecked.push(i); //入次数が0の頂点をキューに入れる
      l_depth[i] = 0; //そのような頂点は深さが0
    }
  }
  while(!unchecked.empty()){
    int current = unchecked.front();
    unchecked.pop();
    ans.push_back(current); //キューから取り出したらすぐソート後のリストに加える

    for(int next: G[current]){ //「行ける」頂点について
      h[next]--; //入次数を減らす
      l_depth[next] = max(l_depth[next], l_depth[current]+1); //最長経路
      if(h[next]==0){ //入次数0になったらキューに追加
        unchecked.push(next);
      }
    }
  }
}

int main(){
  input();

  l_depth.resize(N, -1);
  topoBFS();

  bool isDAG = ans.size()==N; //DAGであるかどうか
  if(isDAG){
    for(int x: ans){
      cout<<x<<endl; //1始まりで出力するときはx+1とする
    }
  }else{
    cout<<"DAGではない"<<endl;
  }
}

提出結果↓

https://onlinejudge.u-aizu.ac.jp/status/users/ohys/submissions/1/GRL_4_B/judge/4493059/C++14

最初の入力例を入れると次のようになる（頂点の数は1始まり）

1
6
2
4
5
3
7

ずばり、最初の方のトポロジカルソートの図と同じである。

ちなみに、入力として $7 \rightarrow 2$ の情報をつける（閉路をつくる）と次のようになる（入力の辺の数が9になっていることに注意）

//入力
7 9
1 2
1 4
2 3
2 5
4 3
5 7
6 4
6 5
7 2
//出力
DAGではない

最長経路

DAGの中で、一番長く道を取れるのはどこか、ということ。例のグラフを（変形してたら不恰好になってしまったが）再掲。各頂点の「深さ」で色分けしている。

黄色が深さ0、緑が1、青が2、赤が3 である。頂点5は、$6 \rightarrow 5$ と行けば深さ1では？という考え方もあるが、とにかくより深いルートを取るので、$1 \rightarrow 2 \rightarrow 5$ を採用して深さ2である。

最長経路は、$1 \rightarrow 2 \rightarrow 5 \rightarrow 7$ と潜れば最大の $3$ である。

これを求めるのに必要なのが先ほどのプログラムに紛れ込んでいたl_depth配列である。

とはいっても、最初に黄色の頂点をキューにいれるついでにそこの深さを0として、あとはキューから頂点currentを取り出すたびに、「行ける」頂点nextについて以下の処理を行うだけである。

l_depth[next] = max(l_depth[next], l_depth[current]+1); //最長経路

ABC139-Eに適用する

本問では、$N$ 人が総当たりで行う全 $N(N-1)/2$ 試合を入力に従ってグラフ化し、閉路がなければ最大経路長を取る。という問題である。

入力例2を条件に沿ってグラフにすると次のようになる（1-2 は選手1対選手2 を示す）。各試合の前後関係が矢印の順番になっていないといけないということである。

//ABC139-E入力例2
4
2 3 4 //1が対戦する順番は 2->3->4 という意味
1 3 4
4 1 2
3 1 2

今までの考えを適用できそうだ。

ただ、難しいのが、試合に通し番号をつけて管理するということである。1対2は2対1と同じことだから、同じ試合として頂点の処理をしなければいけない。 以下のように辞書式に割り振るのが妥当であろう。ここでは0始まりにする。

試合	1-2	1-3	1-4	2-3	2-4	3-4
番号	0	1	2	3	4	5

最初これを計算で出そうとしていたが面倒で失敗した。しかし明快な方法がある。ヒントはこのページだった。↓

AtCoder Beginner Contest 139 - E - League(グラフを使う)

以下のように2変数から試合番号を取り出せるテーブルを用意しておけば良い（選手の番号も0始まりに注意）。自分と対戦することはないので自分対自分は-1としておく

i対j	0	1	2	3
0	-1	0	1	2
1	0	-1	3	4
2	1	3	-1	5
3	2	4	5	-1

これの作り方は簡単である。

//nは選手の人数
vector<vector<int>> IDs(n, vector<int>(n, -1));
int id = 0;
for(int i=0; i<n; i++){
  for(int j=i+1; j<n; j++){
    IDs[i][j] = id;
    IDs[j][i] = id;
    id++;
  }
}

次に問題になるのが入力の受け取り方である。入力例2を考える。

4
2

この段階では何もしない

4
2 3

ここで、試合1-2 → 試合1-3 という辺を構成する。

4
2 3 4

ここでさらに、試合1-3 → 試合1-4 という辺を構成する。これらは、先ほどの試合番号を使って基本のグラフ入力に置き換えれば

0 1
1 2
...

という意味になる。これを実現するには

int t, bufid, vsid;
for(int i=0; i<n; i++){
  bufid = -1;
  for(int j=0; j<n-1; j++){
    cin>>t;t--;
    vsid = IDs[i][t];

    if(bufid != -1){
      G[bufid].push_back(vsid);
      h[vsid]++;
    }

    bufid = vsid;
  }
}

これで、先ほどの試合関係の図は次のように変換される

つまり、基本のグラフ入力形式にすると（頂点=試合数 $N(N-1)/2$ 辺の数 $N(N-2)$）

6 8
0 1
1 2
0 3
3 4
5 1
1 3
5 2
2 4

である。これをトポロジカルソートプログラムに入力すると出力は

0
5
1
2
3
4

である。つまり「トポロジカルソート可能$\Leftrightarrow$DAGである」といえる。ちなみに、ソートした各頂点の深さを出力させるようにすると以下のようになる。

//書き換え
  if(isDAG){
    for(int x: ans){
      cout<<x<<", "<<l_depth[x]<<endl;
    }
  }

//出力
0, 0
5, 0
1, 1
2, 2
3, 2
4, 3

ここでのl_depthは、試合を行うべき日数を0始まりで示していると言える。ABC139-E入力例2にある通り、

• 0日目に試合番号0,5 すなわち1対2と3対4
• 1日目に試合番号1 すなわち1対3
• 2日目に試合番号2,3 すなわち1対4と2対3
• 3日目に試合番号4 すなわち2対4

をやれば良いということである。つまりはl_depthの最大値(+1)が試合の消化に必要な日数である。

以下のコードでは

int l_max = *max_element(l_depth.begin(), l_depth.end());

としたが、トポロジカルソートの結果を利用して

int l_max = l_depth[ans.back()];

でもAC。

ABC139-Eに提出

以上を統合して、ABC139-Eに提出できるコードに書き換えると次のようになる。最初に作ったトポロジカルソートをする関数topoBFSには一切手を加えていない。頂点数 $N$ は、入力したnより $N=n(n-1)/2$として設定する。

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

int N; //頂点の数
vector<vector<int>> G; //グラフ
vector<int> h; //入次数
vector<int> l_depth; //最大経路長
vector<int> ans; //トポロジカルソート結果を格納

void input(){
  int n;
  cin>>n;
  vector<vector<int>> IDs(n, vector<int>(n, -1));
  N = n*(n-1)/2;
  G.resize(N);
  h.resize(N, 0);
  l_depth.resize(N, -1);

  int id = 0;
  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      IDs[i][j] = id;
      IDs[j][i] = id;
      id++;
    }
  }

  int t, bufid, vsid;
  for(int i=0; i<n; i++){
    bufid = -1;
    for(int j=0; j<n-1; j++){
      cin>>t;t--;
      vsid = IDs[i][t];

      if(bufid != -1){
        G[bufid].push_back(vsid);
        h[vsid]++;
      }

      bufid = vsid;
    }
  }
}

void topoBFS(){   
  queue<int> unchecked;
  for(int i=0; i<N; i++){
    if(h[i]==0){
      unchecked.push(i); //入次数が0の頂点をキューに入れる
      l_depth[i] = 0; //そのような頂点は深さが0
    }
  }
  while(!unchecked.empty()){
    int current = unchecked.front();
    unchecked.pop();
    ans.push_back(current); //キューから取り出したらすぐソート後のリストに加える

    for(int next: G[current]){ //「行ける」頂点について
      h[next]--; //入次数を減らす
      l_depth[next] = max(l_depth[next], l_depth[current]+1); //最長経路
      if(h[next]==0){ //入次数0になったらキューに追加
        unchecked.push(next);
      }
    }
  }
}

int main(){
  input();
  
  topoBFS();

  bool isDAG = ans.size()==N;
  if(isDAG){
    int l_max = *max_element(l_depth.begin(), l_depth.end()); //l_depthの最大値をとる
    cout<<l_max+1<<endl;
  }else{
    cout<<-1<<endl;
  }
}

提出結果→https://atcoder.jp/contests/abc139/submissions/13431918

おしまい

また一つアルゴリズムを習得できた。紆余曲折あったがACできてよかった。

閉路検出を再帰DFSでもできるそうだが、なかなか理解できない。使えるようにしておきたい。

参考

• トポロジカルソートのアルゴリズム（閉路のない有向グラフDAGのソート） | アルゴリズムロジック
• トポロジカルソート - AOJ
• AtCoder Beginner Contest 139 - E - League(グラフを使う)