union find木の実装

Question

前提

今union find木の勉強をしているのですが、コード自体は蟻本に書いているものをそのままパクってきたのですが、なぜかエラーが出ます。

発生している問題・エラーメッセージ

./Main.cpp: In function ‘void init(int)’:
./Main.cpp:10:12: error: reference to ‘rank’ is ambiguous
   10 |            rank[i] = 0;
      |            ^~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/nested_exception.h:40,
                 from /usr/include/c++/9/exception:144,
                 from /usr/include/c++/9/ios:39,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from ./Main.cpp:1:
/usr/include/c++/9/type_traits:1257:12: note: candidates are: ‘template<class> struct std::rank’
 1257 |     struct rank
      |            ^~~~
./Main.cpp:6:15: note:                 ‘std::vector<int> rank’
    6 |    vector<int>rank(MAX_int);
      |               ^~~~
./Main.cpp: In function ‘void unite(int, int)’:
./Main.cpp:19:11: error: reference to ‘rank’ is ambiguous
   19 |        if(rank[x] <rank[y])par[x] == y;
      |           ^~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/nested_exception.h:40,
                 from /usr/include/c++/9/exception:144,
                 from /usr/include/c++/9/ios:39,
                 from /usr/include/c++/9/ostream:38,
                 from /usr/include/c++/9/iostream:39,
                 from ./Main.cpp:1:
/usr/include/c++/9/type_traits:1257:12: note: candidates are: ‘template<class> struct std::rank’
 1257 |     struct rank
      |            ^~~~
./Main.cpp:6:15: note:                 ‘std::vector<int> rank’
    6 |    vector<int>rank(MAX_int);
      |               ^~~~
./Main.cpp:19:20: error: reference to ‘rank’ is ambiguous
   19 |        if(rank[x] <rank[y])par[x] == y;
      |                    ^~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/nested_exception.h:40,
                 from /usr/include/c++/9/exception:144,
                 from /usr/include/c++/9/ios:39,
                 f...

該当のソースコード

#include <iostream>
#include<vector>
using namespace std;
static const int MAX_int = 100000000;
   vector<int>par(MAX_int);
   vector<int>rank(MAX_int);
   void init(int n){
       for(int i=0;i<n;i++){
           par[i] = i;
           rank[i] = 0;
       }
   }
   int find(int x){
       if(par[x] == x)return x;
       else return par[x] == find(par[x]);
   }
   void unite(int x,int y){
       x = find(x);y = find(y);if(y == x)return;
       if(rank[x] <rank[y])par[x] == y;
       else {
           par[y] == x;
           if(rank[x] == rank[y])rank[x]++;
       }
   }
   bool same(int x,int y){
       return find[x] == find[y];
   }
int main(void){
   int N,M;cin >> N >> M;
    vector<pair<int,int>>a(M);
    for(int i=0;i<M;i++){
        cin >> a[i].first >> a[i].second;
    }
    map<int,int>b;
    for(int i=0;i<M;i++){
        b[a[i].first-1]++;b[a[i].second-1]++;
    }
    bool ans = false;
    for(int i=0;i<M;i++){
        if(same(a[i].first ,a[i].second))ans = true;
        unite(a[i].first,a[i].second);
    }
    for(int i = 0;i<N;i++){
        if(b[i] > 2 || ans){
            cout << "No" << endl;return 0;
        }
    }
    cout << "Yes" << endl;
}

試したこと

補足情報（FW/ツールのバージョンなど）

int関数の中は無視してください。

Comments

[Zuishin]

> ./Main.cpp:10:12: error: reference to ‘rank’ is ambiguous

'rank' が曖昧。

> /usr/include/c++/9/type_traits:1257:12: note: candidates are: ‘template<class> struct std::rank’

候補は 'template<class> struct std::rank'

> ./Main.cpp:6:15: note: ‘std::vector<int> rank’

そして 'std::vector<int> rank'

Answer 1

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

https://qiita.com/ofutonton/items/c17dfd33fc542c222396