【leetcode】547. モーメンツとコレクション

タイトル
クラスには学生がN人います.中には友达もいれば、そうではない人もいます.彼らの友情には伝達性がある.AがBの友达、BがCの友达であることが知られているならば、私たちはAもCの友达だと思っています.モーメンツとは、すべての友人の集合を指す.
クラスの中学生間の友人関係を表すN*Nの行列Mを与えた.M[i][j]=1であれば、i番目とj番目の学生が互いに友人関係であることが知られていることを示し、そうでなければ知らない.すべての学生の既知のモーメンツの総数を出力しなければなりません.
例1:
入力:[[1,1,0],[1,1,0],[0,0,1]]出力:2説明:学生0と学生1は互いに友达であり、彼らは友达の輪にいることが知られている.2番目の学生は自分でモーメンツにいます.だから2を返します.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/friend-circles著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
構想
裸の問題を調べてみました
コード#コード#

class Solution {
public:
    class unionSet {
        vector fa;
    public:
        unionSet(int n = 0) : fa(n) {
            for (int i = 0; i < n;i ++) fa[i] = i;
        }
        int get(int x) {
            return fa[x] = (fa[x] == x ? x : get(fa[x]));
        }
        void merge(int a, int b) {
            fa[get(a)] = get(b); 
        }
        int count() {
            int cnt = 0;
            for (int i = 0; i < fa.size(); i++) {
                cnt += (fa[i] == i);
            }
            return cnt;
        }
    };
    int findCircleNum(vector>& M) {
        unionSet u(M.size());
        for (int i = 0; i < M.size(); i++) {
            for (int j = i; j < M.size(); j++) {
                if (M[i][j] == 1) u.merge(i,j);
            }
        }
        return u.count();
    }
};

実行時間:20 ms、すべてのC++コミットで97.49%のユーザーを破った
まとめ

とセットを調べた個数は,遍歴中のfa[i]==iの個数

である.