牛客：计算朋友圈（并查集练习）

题目描述（传送门）

假设有N个用户，其中有些人是朋友，有些则不是。A和B是朋友，B和C是朋友，这样ABC就是一个朋友圈，请计算给定的朋友关系的朋友圈数。
给定一个 N * N 的矩阵 M，表示用户之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个人互为朋友关系，否则为不知道。你必须输出所有用户中的已知的朋友圈总数。

输入描述:
第一行输入为表示用户数N
第2到1+N行表示朋友之间关系，如果值为1表示有朋友关系


输出描述:
输出朋友圈数

示例1

输入
3
1,1,0
1,1,0
0,0,1
输出
2

说明
第0个用户和第1个用户组成一个朋友圈，第2个用户组成一个朋友圈

示例2

输入
3
1,1,0
1,1,1
0,1,1
输出
1
说明
第0，1，2个用户组成了一个朋友圈

解题思路&代码实现

昨天学习了一下并查集，今天就趁热打铁来联系联系。
关于并查集我就不再多说可查看：【高阶数据结构】并查集详解

import java.util.Scanner;

/**
 * @ClassName Test
 * @Description ：TODO
 * @Author Josvin
 * @Date 2021/01/15/21:19
 */
public class Test {
    public static int count ;
    private static int[] id;
    private static int[] size;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int num = Integer.parseInt(s);
        int[][] M = new int[num][num];
        //牛客上练习，对输入输出的处理要一定熟练，自己感觉处理的不是特别好，如果有更好的方法可以交流交流
        for (int i = 0; i < num; i++) {
            String[] str = scanner.nextLine().split(",");
            for (int j = 0; j < num; j++) {
                M[i][j] = Integer.parseInt(str[j]);
            }
        }
        Union_Find(M); //调用并查集
        System.out.println(count);

    }
    private static void Union_Find(int[][] M) {
        int N = M.length;// M的长度也就是总共的人数，也就是上个博客提到的集合总数
        id = new int[N];// id 定义一个集合，大小为 N，也就是总共有N个人
        count = N;// 朋友圈的数目，刚开始每个人就是一个朋友圈，初始化为N
        size = new int[N];// 记录每个朋友圈的大小，在合并时用
        // 初始化id数组，每个人都是一个朋友圈，将置为不同的数即可
        // size 刚开始每个人都是一个朋友圈，他们的大小也就是1
        for (int i = 0; i < N; i++) {
            id[i] = i;
            size[i] = 1;
        }
        //合并，将M数组元素，为1的，合并两者i和j
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (M[i][j] == 1) {
                    Union(i,j);
                }
            }
        }
    }
    // 合并
    private static void Union(int i, int j) {
        int root1 = Find(i);
        int root2 = Find(j);
        if (root1 == root2) {
            return;
        }
        if (size[i] > size[j]) {
            id[root1] = root2;
            size[root2] += size[root1];
        } else {
            id[root2] = root1;
            size[root1] += size[root2];
        }
        count--;
    }
    // 查找
    private static int Find(int p) {
        if (p != id[p]) {
            id[p] = Find(id[p]);
        }
        return id[p];

    }
}

本文地址：https://blog.csdn.net/weixin_45532227/article/details/112689400