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

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

ただいまの
回答率

88.36%

C++の参照渡しについて

解決済

回答 2

投稿 編集

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

cinnamoroll

score 14

 前提・実現したいこと

UnionFind木を構築したのですが、参照渡しがうまくいっていないのか関数の外の配列の値が更新されていません。

テストケースでは頂点数をn、辺の数をkとして、k組の頂点対を与えることを想定しています。

UnionFindの実行後のtree1の値は任意の連結頂点間で等しい値であり、任意の非連結頂点間で異なる値になるはずなのですが、初期化したtree1[i] = iの値のままでした。

 想定される実行結果

入力
5 3
0 2
1 4
2 4

出力
0 0 0 3 0

 該当のソースコード

#include "bits/stdc++.h"
using namespace std;

int root(vector<int>& tree, vector<int>& child, int i){
  if(i == tree[i]){
    for(int j = 0; j < child.size(); j++){
      tree[child[j]] = i;
      child.clear(); 
      return i;
    }
  }
  else{
    child.push_back(i);
    return i = root(tree,child,tree[i]);
  }
}

int unit(vector<int>& tree, vector<int>& child, int x,int y){
  x = root(tree,child,x);
  y = root(tree,child,y);
  tree[max(x,y)] = min(x,y);
}

bool isUnit(vector<int>& tree, vector<int>& child, int x,int y){
  return root(tree,child,x) == root(tree,child,y);
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);  

  int n,k;
  cin >> n >> k;

  vector<int> tree1(n),child1;
  for(int i = 0, i < n; i++) tree1[i] = i; // 初期化

  for(int i = 0; i < k; i++){
    int x,y;
    cin >> x >> y;
    unit(tree1,child1,x,y);
  }

  for(int i = 0; i < n; i++) cout << tree[i] << " ";

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • tiitoi

    2018/11/02 18:54 編集

    マクロが多くて読みづらいです。C++ でマクロは極力使わないほうがよいです。

    キャンセル

  • cinnamoroll

    2018/11/02 18:58

    競技プログラミングで使用しているコードなのでマクロを使用する前提となっています。実務で使う場合には可読性を重視するつもりです。

    キャンセル

  • cateye

    2018/11/02 19:49 編集

    >#define int long long・・・intは予約語ですが?まぁ、マクロだからいいっちゃいいんですが・・・

    キャンセル

  • cinnamoroll

    2018/11/02 20:03

    競技プログラミングでは条件によって32bitに収まらない値を扱うので、オーバーフローの対策としてintをlong longにしています。その関係でint main()がlong long main()となってしまいエラーが発生するので、signed main()に置き換えてあります。

    キャンセル

回答 2

checkベストアンサー

+1

これコンパイラ通りますか?
root関数で値を返せないパターンがあります。
で、そのパターンに最初に当たります。

int root(vector<int>& tree, vector<int>& child, int i){
  if(i == tree[i]){              ←ここが最初成り立つが、childのサイズは0なので
    for(int j = 0; j < child.size(); j++){
      tree[child[j]] = i;
      child.clear(); 
      return i;
    }
  }
  else{
    child.push_back(i);
    return i = root(tree,child,tree[i]);
  }
}


if(i == tree[i]){

ここが最初成り立つが、childのサイズは0なのでループせずに終わる。
しかし、returnがない。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/11/02 19:59

    もともと想定していたコードではfor文に{}をつけずにtree[child[j]] = i;のみをループするつもりだったところで下の2文もループに含んでいたことが原因だったようです。
    c++では返り値を用意しなくてもeaxレジスタの値を自動で返すためコンパイルを通ってしまい発見できなかったようです。
    ありがとうございました。

    キャンセル

0

スース読んでないですが・・・
下記、warningの説明が出来ますか? 出来ない場合はwarningが起きないソースにしましょう。

usr~/test/cpp % g++ t.cpp
t.cpp: In functionlong long int root(std::vector<long long int>&, std::vector<long long int>&, long long int)’:
t.cpp:10:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for(int i=(a);i<(b);i++)
                                   ^
t.cpp:12:19: note: in expansion of macro ‘FOR’
 #define REP(i,n)  FOR(i,0,n)
                   ^
t.cpp:23:5: note: in expansion of macro ‘REP’
     REP(j,child.size()){
     ^
t.cpp: In functionlong long int unit(std::vector<long long int>&, std::vector<long long int>&, long long int, long long int)’:
t.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
t.cpp: In functionlong long int root(std::vector<long long int>&, std::vector<long long int>&, long long int)’:
t.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
usr~/test/cpp % ./a.out 
5 3
0 2
Segmentation fault (core dumped)
usr~/test/cpp % ./a.out 

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/11/02 19:07 編集

    ちなみに、clang++ 8.0でコンパイルすると‘48 warnings generated.’と言われます^^;

    キャンセル

  • 2018/11/02 19:09

    intとunsigned

    キャンセル

  • 2018/11/02 19:12

    intとunsigned intを比較していますが、マクロの性質上intが負になることがないので問題ありません。rootは戻り値をvoidにしていないことが原因ですが本質的な問題点では無いと思われます。

    キャンセル

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

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

関連した質問

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