【競技プログラミング】AtCoder Beginner Contest 315: E - Prerequisites

Question

質問の概要

トポロジカルソートと DFS に関する問題で、AC コードで考慮できていて WA コードでは考慮できていないケースパターン (グラフの例) を教えてほしいです。

問題

AtCoder Beginner Contest 315: E - Prerequisites の問題を解きました。
https://atcoder.jp/contests/abc315/tasks/abc315_e

問題文を要約すると、以下のようになります。

有向非巡回グラフ (ただし連結成分が 1 つとは限らない) が与えられる。ノード 1 から到達できるノード集合に対してトポロジカルソートを行い、ソート結果を出力せよ。

方針

以下の方針でこの問題を解きました。

1. ノード 1 と同じ連結成分に含まれるノードを全列挙する必要がある。これをノード 1 を 始点 とした有向グラフを構築し、そのグラフ上で DFS を行うことで実現する。
2. ノード 1 が 終点 となる方向でトポロジカルソートを行う必要があるため、手順 1 とは逆方向の有向グラフを構築し、そのグラフ上でトポロジカルソートを行う。
3. トポロジカルソート時に訪れる対象となるノードは、手順 1 の DFS で到達できたノードに限定しなければならない。

疑問点

この考えを元に実装したコードが以下になりますが、WA となりました。
https://atcoder.jp/contests/abc315/submissions/44743639

こちらは上記コードを修正し、AC となったコードです。
https://atcoder.jp/contests/abc315/submissions/44773681

違う点はトポロジカルソート関数中のコメントが書かれた if の条件だけです。正確には出力部分も微妙に異なりますが、おそらく本質ではない箇所だと思われます。

vector<int> topological_sort(vector<vector<int>> &graph, vector<int> &deg, vector<int> &visited){
  int len=graph.size();
  vector<int> res;
  
  queue<int> que;
  rep(i,1,len){
    if(deg[i]==0&&visited[i]) que.push(i);
  }

  while(!que.empty()){
    int v=que.front(); que.pop();
    rep(i,0,int(graph[v].size())){
      int u=graph[v][i];
      deg[u]--;
      // if(deg[u]==0) que.push(u);  // WA コードはこっち
      if(deg[u]==0&&visited[u]) que.push(u);  // AC コードはこっち
    }
    res.push_back(v);
  }

  return res;
}

WA コードでこのように if の条件を設定した理由ですが、トポロジカルソート開始前に探索開始箇所を queue に入れる際、7 行目の if で DFS で到達できたノードだけを入れているため、while 部分で辿られるノードはそこから繋がるノード、つまり DFS で到達できたノードしか有り得ないと考えたからです。

ですが、while 部分にも「DFS で到達できたか？」の条件を加えることで AC となったため、上記の考えは誤りだったと考えています。

そこで、WA コードで上手く答えを出せないグラフの例を考えてみたのですが、一向にわかりません。どなたかわかる方はいらっしゃいますでしょうか？

Answer 1

こちらでいかがでしょうか。

3
1 3
1 3
0

別のパターンを思いついたので追記します。

3
1 3
1 1
0

Comments

[RinT_hinabita39]

解決しました、ありがとうございます。

「本質ではない」と考えていた出力部分についても、今回のトポロジカルソートのアルゴリズムと組み合わせると問題が発生することも判明しました。

実は、回答者さんが提示されたものと似たグラフパターンとして、問題で提示されている入力例 3 を改変した以下のパターンは試していました。こちらは正しい答えが出ていたので、ちゃんと対応ができていると思い込んでおり、その先に進めていませんでした (こちらが通って回答者さんが提示されたものが通らない原因も理解しました)。

```
8
1 5
2 5 6
1 7
1 8
0
0
0
0
```