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

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

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

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

C++

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

Q&A

解決済

1回答

1158閲覧

AtcoderRegularContest037 B問題「バウムテスト」をunion-find木で解く方法

tutomu1999

総合スコア1

アルゴリズム

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

C++

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

0グッド

0クリップ

投稿2020/11/30 11:57

こんばんは.初めて質問します.
この度は,何度もソースコードを見直したのですが,どこが間違っているかわからなかったため質問いたします
AtcoderRegularContest037 B問題「バウムテスト」についての質問なのですが,
以下のソースコードで提出してもWAが出てしまいます.

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

該当のソースコード

C++

1#include<bits/stdc++.h> 2using ll= long long; 3#define REP(i,n) for(ll i=0;i<ll(n);i++) 4 5using namespace std; 6/*..................DEFINE GLOBAL VARIABLES...................*/ 7int N,M; 8 9int par[1000]; 10int ht[1000]; 11/*.....................DEFINE FUNCTIONS ......................*/ 12void init(int n){ 13 REP(i,n){ 14 par[i]=i; 15 } 16} 17 18int root(int x){ 19 if(par[x]==x) return x; 20 else return par[x]=root(par[x]); 21} 22 23void unite(int x,int y){ 24 x=root(x); 25 y=root(y); 26 if(x==y) return; 27 if(ht[x] < ht[y]){ 28 par[x] = y; 29 }else{ 30 par[y] = x; 31 if(ht[x] == ht[y]){ 32 ht[x]++; 33 } 34 } 35} 36 37bool same(int x,int y){ 38 return root(x)==root(y); 39} 40/*.........................kemkemG0...........................*/ 41int main() { 42 cin>>N>>M; 43 44 int ng[1000]; 45 46 init(110); 47 48 REP(i,M){ 49 int v,w; 50 cin>>v>>w; 51 v--;w--; 52 if(same(v,w)){ 53 ng[root(v)]=-1; 54 continue; 55 } 56 else unite(v,w); 57 } 58 59 REP(i,N){ 60 if(ng[i]==-1) ng[root(i)]=-1; 61 } 62 63 int count=0; 64 65 for(int i=0;i<N;i++){ 66 if(root(i)==i&&ng[i]==0) count++; 67 } 68 69 cout<<count<<endl; 70} 71 72

考えたこと

0.union-find木を初期化する.
1.点たちをつなぐ.既に同じ木にいる2点の間を結ぶとき閉路ができるはずなので,その根xに対してng[x]=-1としておく.(このときの根は最終的に根じゃないかもしれないので,次の操作2をしています)
2.ng[i]=-1となる点を持つ木の根のngも-1とする.
3.root(i)=iかつng[i]=0となる点が木の個数であるからそれを出力する.

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

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

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

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

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

guest

回答1

0

ベストアンサー

ngが初期化されていません

投稿2020/11/30 12:06

yudedako67

総合スコア2047

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

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

tutomu1999

2020/11/30 12:17

解答ありがとうございます. ng[1000]={}; と初期化したらうまくいきました. int ng[1000]; と書くだけで勝手に初期化されると思っていたんですが,そうでないんですね(c++に入門したてなのであんまりそこがわかっていませんでした)
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.35%

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

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

質問する

関連した質問