ACL Beginner ContestのC問題"Connect cities"の自分の回答がいくつかのテストケースでWAになる

Question

2020/9/26に行われたatcoderのACL問題なのですが、リンク内容
このC問題をAOJのリンク内容を参考にして以下のコードで解いたのですが、いくつかのケースでWAになってしまいます。どこが悪いのか教えていただけますか。

#include <iostream>
#include <vector>

using namespace std;

class DisjointSet{
    public:
        vector<int> rank, p;
        DisjointSet(){}
        DisjointSet(int size){
            rank.resize(size, 0);
            p.resize(size, 0);
            for(int i = 1; i < size; i++){
                p[i] = i;
                rank[i] = 0;
            }
        }

        void unite(int x, int y){
            link(findSet(x), findSet(y));
        }

        void link(int x, int y){
            if(rank[x] > rank[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank[x] == rank[y]){
                    rank[y]++;
                }
            }
        }

        int findSet(int x){
            if(x != p[x]){
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
};

int main()
{
    int n, a, b, m;
    int cnt = 0;
    cin >> n >> m;
    DisjointSet ds = DisjointSet(n + 1);
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        ds.unite(a, b);
    }
    int x;
    for(int i = 2; i <= n; i++){
        if(ds.p[1] != ds.p[i]){
            ds.unite(i, 1);
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;

}

Answer 1

        if(ds.p[1] != ds.p[i]){
            ds.unite(i, 1);
            cnt++;
        }

おそらく同じ集合に含まれるかを調べたかったのだと思いますが、そのためには親を直接比較してはだめで、ルート同士を比較しないといけません。

Comments

[rdld036]

関数unite()でfindSet()を呼び出しており、そこで木のそれぞれの要素の親を一律に根に揃えていると思うのですが、それでは根を比較したことにならないのでしょうか。

[yudedako67]

findSetでルートが親に設定されるのは、その要素からルートへの経路上に存在する要素だけなので他はそのままです。さらにその後にuniteで一方のルートに新しい親が設定されるので、もともとそのルートに属していた要素は親とルートが違う状態に戻ります。

[rdld036]

確かに関数linkは一方のルートの親のみを相手のルートに設定しているだけですね。的確にアドバイスをしてくださりありがとうございます。