Friend Circles

https://leetcode.com/problems/friend-circles/description/

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is adirectfriend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ithand jthstudents are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Thoughts

01矩阵元素(i,j)值为1表示(i,j)是一个圈子的，问最后一共有多少圈子。牵扯到集合查询和合并，UF。

Code

/*
 * @lc app=leetcode id=547 lang=cpp
 *
 * [547] Friend Circles
 */

// @lc code=start
class Solution {
public:
    class UF {
    public:
        vector<int> parents;
        int size;
        UF(int N): parents(N), size(N) {
            for (int i = 0; i < N; ++i) {
                parents[i] = i;
            }
        }
        void un(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                parents[x] = y;
                --size;
            }
        }
        int find(int x) {
            while (x != parents[x]) {
                x = parents[x];
                parents[x] = parents[parents[x]];
            }
            return x;
        }
    };

    int findCircleNum(vector<vector<int>>& M) {
        const int N = M.size();
        UF uf(N);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (M[i][j] == 1) {
                    uf.un(i, j);
                }
            }
        }
        return uf.size;
    }
};
// @lc code=end

Analysis

空间复杂度是O(N). 时间复杂度小于O(N^3).