質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.53%
ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

Q&A

解決済

1回答

293閲覧

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

RinT_hinabita39

総合スコア28

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

0グッド

0クリップ

投稿2023/08/23 20:31

質問の概要

トポロジカルソートと 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 の条件だけです。正確には出力部分も微妙に異なりますが、おそらく本質ではない箇所だと思われます。

cpp

1vector<int> topological_sort(vector<vector<int>> &graph, vector<int> &deg, vector<int> &visited){ 2 int len=graph.size(); 3 vector<int> res; 4 5 queue<int> que; 6 rep(i,1,len){ 7 if(deg[i]==0&&visited[i]) que.push(i); 8 } 9 10 while(!que.empty()){ 11 int v=que.front(); que.pop(); 12 rep(i,0,int(graph[v].size())){ 13 int u=graph[v][i]; 14 deg[u]--; 15 // if(deg[u]==0) que.push(u); // WA コードはこっち 16 if(deg[u]==0&&visited[u]) que.push(u); // AC コードはこっち 17 } 18 res.push_back(v); 19 } 20 21 return res; 22}

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

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

3 1 3 1 3 0

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

3 1 3 1 1 0

投稿2023/08/23 21:22

編集2023/08/26 00:29
actorbug

総合スコア2205

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

RinT_hinabita39

2023/08/24 03:37 編集

解決しました、ありがとうございます。 「本質ではない」と考えていた出力部分についても、今回のトポロジカルソートのアルゴリズムと組み合わせると問題が発生することも判明しました。 実は、回答者さんが提示されたものと似たグラフパターンとして、問題で提示されている入力例 3 を改変した以下のパターンは試していました。こちらは正しい答えが出ていたので、ちゃんと対応ができていると思い込んでおり、その先に進めていませんでした (こちらが通って回答者さんが提示されたものが通らない原因も理解しました)。 ``` 8 1 5 2 5 6 1 7 1 8 0 0 0 0 ```
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.53%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問