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

Question

前提・実現したいこと

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] << " ";

}

Comments

[tiitoi]

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

[cinnamoroll]

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

[cateye]

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

[cinnamoroll]

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

Answer 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がない。

Comments

[cinnamoroll]

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

Answer 2

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

usr~/test/cpp % g++ t.cpp
t.cpp: In function ‘long 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 function ‘long 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 function ‘long 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 

Comments

[cateye]

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

[cinnamoroll]

intとunsigned

[cinnamoroll]

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