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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Visual C++

Microsoft Visual C++はWindowsのCとC++の統合開発環境(IDE)であり、コンパイラやデバッガを含んでいます。

Visual Studio

Microsoft Visual StudioはMicrosoftによる統合開発環境(IDE)です。多種多様なプログラミング言語に対応しています。

デバッグ

デバッグはプログラムのバグや欠陥を検知し、開発中のバグを取り除く為のプロセスを指します。

C++

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

Q&A

解決済

1回答

612閲覧

AIZU ONLINE JUDGEのDSL_1_AでREになってしまう理由が分かりません。

sumachu

総合スコア22

Visual C++

Microsoft Visual C++はWindowsのCとC++の統合開発環境(IDE)であり、コンパイラやデバッガを含んでいます。

Visual Studio

Microsoft Visual StudioはMicrosoftによる統合開発環境(IDE)です。多種多様なプログラミング言語に対応しています。

デバッグ

デバッグはプログラムのバグや欠陥を検知し、開発中のバグを取り除く為のプロセスを指します。

C++

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

0グッド

0クリップ

投稿2020/05/09 06:07

DSL_1_Aで以下の以下のコードを提出したところREになっていまいます。入力例でデバッグしてみたところ、com=0, x=1, y=3のクエリでfindSet(1)の戻り値がとても大きな値として、linkメッソドの第一引数に入ってしまうため、インデックスが配列の境界外となり、ランタイムエラーが発生しています。findSetメッソドをコメントアウト部分のように書き換えればREは生じなくなり、Acceptされますが、両者の違いが判りません。以下の提出コードでfindSet(1)の戻り値が記憶されない理由を教えていただきたいです。

C++

1#include <bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4 5class DisjointSet 6{ 7private: 8 vector<int> rank, p; 9 10public: 11 DisjointSet() {} 12 DisjointSet(int size) 13 { 14 rank.resize(size, 0); 15 p.resize(size, 0); 16 for (int i = 0; i < size; i++) makeSet(i); 17 } 18 19 void makeSet(int x) 20 { 21 p[x] = x; 22 rank[x] = 0; 23 } 24 25 bool same(int x, int y) 26 { 27 return findSet(x) == findSet(y); 28 } 29 30 void unite(int x, int y) 31 { 32 link(findSet(x), findSet(y)); 33 } 34 35 void link(int x, int y) 36 { 37 if (rank[y] < rank[x]) p[y] = x; 38 else { 39 p[x] = y; 40 if (rank[y] == rank[x]) rank[y]++; 41 } 42 } 43 44 int findSet(int x) 45 { 46 if (p[x] == x) return p[x]; 47 p[x] = findSet(p[x]); 48 /*if (p[x] != x) p[x] = findSet(p[x]); 49 return p[x];*/ 50 } 51}; 52 53int main() 54{ 55 int n, q; 56 cin >> n >> q; 57 DisjointSet ds(n); 58 for (int i = 0; i < q; i++) { 59 int com, x, y; 60 cin >> com >> x >> y; 61 if (com == 0) ds.unite(x, y); 62 else { 63 if (ds.same(x, y)) cout << 1 << endl; 64 else cout << 0 << endl; 65 } 66 } 67}

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

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

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

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

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

guest

回答1

0

ベストアンサー

現在のコードでは条件が満たされない限りreturnされません
コメントアウトされてるほうのコードでは確実にreturnされます。その違いです。

投稿2020/05/09 06:57

yudedako67

総合スコア2047

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

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

sumachu

2020/05/09 07:33

ご回答ありがとうございます。おかげさまでデバッグの際のミスに気付くことができました。Visual Studioでcom==0&&x==1&&y==3の条件でブレークポイントを打ってデバッグしていましたが、link(findSet(x), findSet(y))の際に、第1引数のfindSet(x)が第2引数のfindSet(y)より先に呼び出されていると勘違いしていました。そのため、回答者様のご回答にたどり着きませんでした。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問