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

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

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

645閲覧

AtcoderRegularContest037 B問題「バウムテスト」が分かりません

chan_yu1224

総合スコア7

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1グッド

0クリップ

投稿2019/08/21 15:03

こんばんは.お世話になっております.
この度は,何度もソースコードを見直したのですが,分からなかったので質問させていただきます.
AtcoderRegularContest037 B問題「バウムテスト」についての質問なのですが,
以下のソースコードで提出してもWAが出てしまいます.

この問題はサンプル以外のテストパターンが公開されておらず,
原因を突き止めることができなかったので,
ソースコード上に問題があれば指摘していただきたいです....

#include <bits/stdc++.h> #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define repr(i, n) for(int i = (int)(n); i >= 0; i--) #define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++) #define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--) #define all(x) (x).begin(),(x).end() #define inf 2e9 using namespace std; typedef long long int lli; typedef long long ll; int main() { //入力処理 int n,m; cin >> n >> m; //mapに格納 unordered_map<int,vector<int>> tree; rep(i,m){ int u,v; cin >> u >> v; u--; v--; tree[u].push_back(v); } //判定処理 int checked = 0, ans = 0; vector<bool> checklist(n,false); while(checked < n){ //次の探索開始場所の決定 int next_search; rep(i,n){ if(!checklist[i]){ next_search = i; break; } } stack<int> st; st.push(next_search); bool isTree = true; //探索開始 while(st.size() > 0){ int now = st.top(); st.pop(); checked++; checklist[now] = true; rep(i,tree[now].size()){ if(!checklist[tree[now][i]]){ st.push(tree[now][i]); //今の頂点の子をスタックに格納 } else{ isTree = false; //既に探索済みの場所を参照すれば閉路確定 } } } if(isTree) ans++; } cout << ans << endl; }

####アルゴリズム
今回私が考えたアルゴリズムは,

1.mapに親頂点をkey,子頂点の集合をvalueとして格納.
2.for文(repマクロを使用しています)で探索開始点を決定.
3.探索済みの頂点をchecklistに記録しつつ深さ優先探索.
3-1.現在参照中の頂点をnowに格納.
3-2.子頂点の集合をスタックstに格納.
3-3.このとき,子頂点のうち一つでも探索済みの頂点を参照すれば,木構造でないと判定.
4.3をスタックの長さが0になるまで繰り返し.
5.2~4を全ての頂点を探索し終えるまで繰り返し.
6.答えを出力.

といった感じです.
WAの原因となりそうなものがあれば指摘を頂きたいです.

bochan2👍を押しています

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

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

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

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

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

guest

回答2

0

全く別の解法ですが

Union Find使って
閉路を検知しつつグラフを構築してやれば
あとは数えるだけです

投稿2019/08/21 23:04

asm

総合スコア15147

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

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

chan_yu1224

2019/08/22 03:35

こんにちは. 回答ありがとうございます. 今日通学中にほかの人のAC解答を眺めていたのですがその人もUnion Findを使用していました. どうやらこの問題はUnion -Find木を使えば楽々解けるみたいですね.... 勉強不足でそもそも存在自体を知りませんでした. とても参考になりました!
guest

0

ベストアンサー

惜しいところまでは行ってると思うので失敗するテストケースだけ

5 4 1 5 3 5 3 4 2 4

このようなテストケースの場合、明らかに[1-5-3-4-2]とつながった閉路のない連結成分が一つだけですが、そのプログラムの出力は[2]です

投稿2019/08/21 16:58

yudedako67

総合スコア2047

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

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

chan_yu1224

2019/08/22 03:31

こんにちは. 回答ありがとうございます. そのテストケースは頭の中になかったです... 私が実装したアルゴリズムだと入力の右側が親,左側が子というように決めつけてしまっていたために題意通りの動作にならなかった訳ですね. 参考になりました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問