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。

解法：并查集

难度:简单

typedef struct Node {
    int *arr;
    int *size;
} Node;

Node *getNewNode(int key) {
    Node *node = (Node *)calloc(sizeof(Node), 1);
    node->arr = (int *)malloc(sizeof(int) * (key + 5));
    node->size = (int *)malloc(sizeof(int) * (key + 5));
    for (int i = 0; i < key; i++) {
        node->arr[i] = i;
        node->size[i] = 1;
    }
    return node;
}

int find(Node *node, int val) {
    if (node->arr[val] == val) return val;
    return (node->arr[val] = find(node, node->arr[val]));
}

int insert(Node *node, int a, int b) {
    int fa = find(node, a), fb = find(node, b);
    //printf("a : %d, b : %d, fa = %d, fb = %d\n", a, b, fa, fb);
    if (node->arr[fa] == node->arr[fb]) return 0;
    if (node->size[fa] < node->size[fb]) {
        fa ^= fb; fb ^= fa; fa ^= fb;
    }
    node->arr[fb] = fa;
    node->size[fa] += node->size[fb];
    return 1;
}


void clear(Node *node) {
    if (node == NULL) return ;
    free(node->arr);
    free(node->size);
    free(node);
    return ;
}

int find_size(Node *node, int la) {
    int cnt = 0;
    for (int i = 0; i < la; i++) {
        if (i != node->arr[i]) cnt += 1;
        //printf("%d\n", node->arr[i]);
    }
    return la - cnt;
}

int findCircleNum(int** M, int MRowSize, int MColSize) {
    if (MRowSize == 1) return 1;
    //printf("%d , %d\n", MRowSize, MColSize);
    Node *node = getNewNode(MRowSize * MColSize);
    for (int i = 0; i < MRowSize; i++) {
        for (int j = i + 1; j < MColSize; j++) {
            if (M[i][j] == 1) 
                insert(node, i, j);
            //insert(node, M[i][i], M[i][j]);
            //printf("ii : %d, ij : %d\n", find(node, M[i][i]), find(node, M[i][j]));
        }
    }
    int cnt = find_size(node, MRowSize);
    //printf("cnt : %d\n", cnt);
    clear(node);
    return cnt;
}