学校的班级个数【并查集基础应用，Java实现】

题目描述

现有一个学校，学校中有若干个班级，每个班级中有若干个学生，每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级，学生B和学生C处于一个班级，那么我们称学生A和学生C也处于一个班级。

现已知学校中共n个学生（编号为从1到n），并给出m组学生关系（指定两个学生处于一个班级），问总共有多少个班级。

输入描述

第一行两个整数n、m（1≤n≤100,1≤m≤100），分别表示学生个数、学生关系个数；

接下来m行，每行两个整数a和b（1≤a≤n,1≤b≤n, a≠b），表示编号为a的学生和编号为b的学生处于一个班级。

输出描述

输出一个整数，表示班级个数。

样例

输入

5 3			// 共5个学生，3对关系
4 2			// 4号学生和2号学生一个班
1 3
2 5

输出

2		// 共两个班

思路分析

• 这种题目第一想法可能是深度遍历的思想，每次从一个未被访问过的点出发走到底，每走到一个节点都标记为已访问，出发的次数即为班级个数。
• 不过这种类型的题目也可以使用并查集来解决，并且效果可能会更好，并查集的基本思路如下👇：
  1. 设立数组father，father[son]存放的是son的父亲节点【即是一个整体的】
  2. 初始son的父亲节点为它本身，也就是father[son]=son
  3. 当传入一对关系时【如a与b节点为一个整体】，a的父亲就会由b的父亲来担任【共享父亲，b的父亲由a的父亲担任也无妨】，从而使得独立的两个小整体融合为一个大整体，这个操作我们称之为Union
• 此题只需要顺着并查集的基本思路，设立数组father将父子关系进行存储即可，最后统计father[i]==i的节点数即为班级个数

代码实现

package homework;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// n 个学生int n = scanner.nextInt();int father[] = new int[n];for (int i = 0; i < n; i++) {father[i] = i;}// m 组关系int m = scanner.nextInt();for (int i = 0; i < m; i++) {// 减1是为了使得编号与数组下标对应上int a = scanner.nextInt() - 1;int b = scanner.nextInt() - 1;// a 与 b 融合为一个整体Union(father, a, b);}int sum = 0;for (int i = 0; i < n; i++) {if (father[i] == i) {sum++;}}System.out.println(sum);}// 寻找下标 son 的父亲节点public static int FindFather(int father[], int son) {if (father[son] == son) {// 自己是自己的爸爸return son;}// 找到son真正的爸爸，并赋值回来【这是个剪枝操作，可以提高查找效率】father[son] = FindFather(father, father[son]);return father[son];}public static void Union(int arr[], int a, int b) {int fatherA = FindFather(arr, a);int fatherB = FindFather(arr, b);// 两个人的爸爸不同，把其中一个的爸爸进行赋值if (fatherA != fatherB) {arr[fatherA] = fatherB;}}}