山东省示范校建设网站,怎么看网站哪个公司做的,亿网联播,鹤壁建设网站推广渠道电话题目描述 现有一个学校#xff0c;学校中有若干个班级#xff0c;每个班级中有若干个学生#xff0c;每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级#xff0c;学生B和学生C处于一个班级#xff0c;那么我们称学生A和学生C也处于一个班级。 现已知学校中共…题目描述 现有一个学校学校中有若干个班级每个班级中有若干个学生每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级学生B和学生C处于一个班级那么我们称学生A和学生C也处于一个班级。 现已知学校中共n个学生编号为从1到n并给出m组学生关系指定两个学生处于一个班级问总共有多少个班级。 输入描述 第一行两个整数n、m1≤n≤100,1≤m≤100分别表示学生个数、学生关系个数 接下来m行每行两个整数a和b1≤a≤n,1≤b≤n, a≠b表示编号为a的学生和编号为b的学生处于一个班级。 输出描述 输出一个整数表示班级个数。 样例
输入
5 3 // 共5个学生3对关系
4 2 // 4号学生和2号学生一个班
1 3
2 5输出
2 // 共两个班思路分析
这种题目第一想法可能是深度遍历的思想每次从一个未被访问过的点出发走到底每走到一个节点都标记为已访问出发的次数即为班级个数。不过这种类型的题目也可以使用并查集来解决并且效果可能会更好并查集的基本思路如下 设立数组fatherfather[son]存放的是son的父亲节点【即是一个整体的】初始son的父亲节点为它本身也就是father[son]son当传入一对关系时【如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;}}}
