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

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

ただいまの
回答率

88.23%

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 948

chan_yu1224

score 7

こんばんは.お世話になっております.
この度は,何度もソースコードを見直したのですが,分からなかったので質問させていただきます.
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の原因となりそうなものがあれば指摘を頂きたいです.

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

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

5 4
1 5
3 5
3 4
2 4


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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/08/22 12:31

    こんにちは.
    回答ありがとうございます.
    そのテストケースは頭の中になかったです...

    私が実装したアルゴリズムだと入力の右側が親,左側が子というように決めつけてしまっていたために題意通りの動作にならなかった訳ですね.
    参考になりました!

    キャンセル

+1

全く別の解法ですが

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/08/22 12:35

    こんにちは.
    回答ありがとうございます.

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

    とても参考になりました!

    キャンセル

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

  • ただいまの回答率 88.23%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る