こんばんは.お世話になっております.
この度は,何度もソースコードを見直したのですが,分からなかったので質問させていただきます.
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の原因となりそうなものがあれば指摘を頂きたいです.
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/08/22 03:35