在最近的学习中我对并查集学得一般懂其原理但用得不深不过在最近Java的期末项目里我的主题是高考模式下的学生成绩管理系统我的思考就停留在了新高考的312的选科目上那是不是同组合的人要放在一块呢结合我最近学过的知识并差集刚好可以写它也许这有点小题大做但我就得自己学的好不好还是实践才知道具体说明如下引用洛谷P1551# P1551 亲戚## 题目描述若某个家族人员过于庞大要判断两个是否是亲戚确实还很不容易现在给出某个亲戚关系图求任意给出的两个人是否具有亲戚关系。规定x 和 y 是亲戚y 和 z 是亲戚那么 x 和 z 也是亲戚。如果 xy 是亲戚那么 x 的亲戚都是 y 的亲戚y的亲戚也都是 x 的亲戚。## 输入格式第一行三个整数 n,m,p,(n,m,p 5000分别表示有 n 个人m个亲戚关系询问 p 对亲戚关系。以下 m行每行两个数 M_iM_j1 M_i,M_j n表示 M_i 和 M_j具有亲戚关系。接下来 p行每行两个数 P_i,P_j询问 P_i 和 P_j 是否具有亲戚关系。## 输出格式p 行每行一个 Yes 或 No。表示第 i个询问的答案为“具有”或“不具有”亲戚关系。输入输出样例输入 #16 5 31 21 53 45 21 31 42 35 6输出 #1YesYesNo很显然这是一个模板题要实现简单的并查集代码如下#include bits/stdc.h using namespace std; const int N100010; int parent[N];//表示它的父节点 int Mysize[N];//表示他的长度即根结点以下挂的长度 int Mystack[N];//提供一个空间去临时存他的状态 void init(int n) { for (int i1;in;i) { parent[i]i;//初始化每个都是自己的父亲 Mysize[i]1;//初始化每个集合的长度都是1 } } //这是非递归写法也可以写成 /* int find(int n){//递归写法也具备压缩性 if(parent[n]!n){ parent[n]find(parent[n]); } return parent[n]; } */ int find(int n) {//find方法是去找他的根节点在这里实现了压缩功能 int size0; while (n!parent[n]) { Mystack[size]n;//压入栈中,收入不是根节点的节点 nparent[n];//找父节点,就是让n向上指直到找到跟节点 } while ( size0) { parent[Mystack[--size]]n;//弹出栈将所有节点都指向根节点 } return n;//返回根节点 } void Union(int x,int y) {//合并两个集合 //首先去找他的根节点 int fxfind(x); int fyfind(y); if (fx!fy) {//在不同的情况下合并,我们这里是大吞小 if (Mysize[fx]Mysize[fy]) {//大的合并到小的 Mysize[fx]Mysize[fy]; parent[fy]fx;//让原来小容量的结点指向大的根节点 }else { Mysize[fy]Mysize[fx];; parent[fx]fy; } } } bool is_same_set(int x,int y) { return find(x)find(y);//判断是否同一个集合 } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m,p;//n个人m个关系p个查询 cinnmp; init(n);//初始化并查集 for(int i0;im;i){ int a,b; cinab; Union(a,b);//合并所有集合 } while(p--0){ int a,b; cinab; if(is_same_set(a,b)){//判断是否同一个集合就说明具有亲戚关系 coutYesendl; }else{ coutNoendl; } } return 0; }而我们在学生成绩管理系统里首先定义UnionFind类代码如下import java.util.*; public class UnionFind { private HashMapStudent, Student parent;//用于记录父节点 private HashMapStudent, Integer rank;//用于记录树的深度,有利于他的合并相当与模板里的Mysize[]; public UnionFind() { parent new HashMap(); rank new HashMap(); } public void addNode(Student s){//添加节点 if(!parent.containsKey(s)){//如果之前节点不存在则添加 parent.put(s, s);//父节点设为自己相当于模板里的parent[x] x; rank.put(s, 1);//树的深度设为1相当于模板里的Mysize[x] 1; } } public Student find(Student s){//查询节点,这里是递归写法 if(parent.get(s) ! s){ parent.put(s, find(parent.get(s))); } return parent.get(s); } public void union(Student s1, Student s2){//合并节点 Student p1 find(s1); Student p2 find(s2); if(p1 ! p2){ if(rank.get(p1) rank.get(p2)){ rank.put(p1, rank.get(p1) rank.get(p2)); parent.put(p2, p1); } else { rank.put(p2, rank.get(p1) rank.get(p2)); parent.put(p1, p2); } } } public boolean isSameSet(Student s1, Student s2){//判断两个节点是否属于同一个集合 return find(s1) find(s2); } }和前面的模板思路相同就是加入学生类和哈希表在测试类里面我们就使用它private static UnionFind uf new UnionFind();//先创建对象作为全局变量方法里的应用public static void addStudent(Student s) throws Exception { synchronized (lock) {//因为我同时用了多线程 String id s.getId(); if (map.containsKey(id)) throw new Exception(学号已存在); map.put(id, s); uf.addNode(s); String comb getCombination(s);//此方法是用于返会所选的几门科目312 /*public static String getCombination(Student s) { return s.getFirstSubject() , s.getSecondSubject1() , s.getSecondSubject2(); }*/ for (Student s1 : map.values()) {//相同组合里的合并到同一个集合里 if (!s1.getId().equals(id) getCombination(s1).equals(comb)) { uf.union(s, s1); break; } } } } //判断学生是否在同已选科目里 public static boolean isSameGroup(String id1, String id2){ Student s1 map.get(id1); Student s2 map.get(id2); if(s1 null || s2 null){ return false; } return uf.isSameSet(s1, s2); } //统计同组合的人数 public static void statGroupSimple() { MapStudent, Integer groupCount new HashMap();//用哈希表类记录个数 for (Student s : map.values()) { Student root uf.find(s); groupCount.put(root, groupcount.getOrDefault(root, 0) 1);//这是简写和以下是一样的 /* if(groupCount.containsKey(root)){ int countgroupCount.get(root); groupCount.put(root,count1); }else{ groupCount.put(root,1); }*/ } System.out.println(选科组合总种类 groupCount.size()); int i 1; for (Student root : groupCount.keySet()) { String combo getCombination(root); int people groupCount.get(root); out.println(第 i 种 组合 combo 人数 people);//一般都用PrintWriter来输出 i; } } //查询同选科的学生用其中一人的学号 public static void showSameGroup(String id) { // 根据学号找学生 Student target map.get(id); if (target null) { out.println(该学号不存在); return; } // 找这个学生根节点 Student root uf.find(target); out.println( 同选科所有同学 ); // 遍历所有学生根节点一样就是同选科 for (Student s : map.values()) { if (uf.find(s) root) { out.println(学号 s.getId() 姓名 s.getName()); } } } //同样的删除也是一个道理 public static void DeleteSameGroup(String id) { // 根据学号找目标学生 Student target map.get(id); if (target null) {//注意要判断一下 System.out.println(学号不存在无法删除); return; } // 找到这个选科组的根节点 Student root uf.find(target); // 先收集要删除的所有学号 ArrayListString deleteList new ArrayList(); for (Student s : map.values()) { if (uf.find(s) root) {//用find方法去找同一集合的学生 deleteList.add(s.getId()); } for (String id : deleteList) { map.remove(id);//通过学号来删除 } }简单总结一下我在写这个管理系统的时候并查集确实是一时想到的使用过程中也改过多次总的来说应用得很浅很浅比起大难的一些算法题来说应用的很浅了力扣情侣牵手逻辑思维上比这个更深以及好多不会写的题目不过这也是我的一个创新吧我也在慢慢实现它其实我对并查集的使用可能解释这个水平了还有好多应用我还没想到的希望大佬们多给建议我的提升空间很大算法的熟练是刷题和应用出来的就好像我听来做左神的课都懂了不写题那就白学了没啥更多好说的加油
在最近的学习中我对并查集学得一般懂其原理但用得不深不过在最近Java的期末项目里我的主题是高考模式下的学生成绩管理系统我的思考就停留在了新高考的312的选科目上那是不是同组合的人要放在一块呢结合我最近学过的知识并差集刚好可以写它也许这有点小题大做但我就得自己学的好不好还是实践才知道具体说明如下引用洛谷P1551# P1551 亲戚## 题目描述若某个家族人员过于庞大要判断两个是否是亲戚确实还很不容易现在给出某个亲戚关系图求任意给出的两个人是否具有亲戚关系。规定x 和 y 是亲戚y 和 z 是亲戚那么 x 和 z 也是亲戚。如果 xy 是亲戚那么 x 的亲戚都是 y 的亲戚y的亲戚也都是 x 的亲戚。## 输入格式第一行三个整数 n,m,p,(n,m,p 5000分别表示有 n 个人m个亲戚关系询问 p 对亲戚关系。以下 m行每行两个数 M_iM_j1 M_i,M_j n表示 M_i 和 M_j具有亲戚关系。接下来 p行每行两个数 P_i,P_j询问 P_i 和 P_j 是否具有亲戚关系。## 输出格式p 行每行一个 Yes 或 No。表示第 i个询问的答案为“具有”或“不具有”亲戚关系。输入输出样例输入 #16 5 31 21 53 45 21 31 42 35 6输出 #1YesYesNo很显然这是一个模板题要实现简单的并查集代码如下#include bits/stdc.h using namespace std; const int N100010; int parent[N];//表示它的父节点 int Mysize[N];//表示他的长度即根结点以下挂的长度 int Mystack[N];//提供一个空间去临时存他的状态 void init(int n) { for (int i1;in;i) { parent[i]i;//初始化每个都是自己的父亲 Mysize[i]1;//初始化每个集合的长度都是1 } } //这是非递归写法也可以写成 /* int find(int n){//递归写法也具备压缩性 if(parent[n]!n){ parent[n]find(parent[n]); } return parent[n]; } */ int find(int n) {//find方法是去找他的根节点在这里实现了压缩功能 int size0; while (n!parent[n]) { Mystack[size]n;//压入栈中,收入不是根节点的节点 nparent[n];//找父节点,就是让n向上指直到找到跟节点 } while ( size0) { parent[Mystack[--size]]n;//弹出栈将所有节点都指向根节点 } return n;//返回根节点 } void Union(int x,int y) {//合并两个集合 //首先去找他的根节点 int fxfind(x); int fyfind(y); if (fx!fy) {//在不同的情况下合并,我们这里是大吞小 if (Mysize[fx]Mysize[fy]) {//大的合并到小的 Mysize[fx]Mysize[fy]; parent[fy]fx;//让原来小容量的结点指向大的根节点 }else { Mysize[fy]Mysize[fx];; parent[fx]fy; } } } bool is_same_set(int x,int y) { return find(x)find(y);//判断是否同一个集合 } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m,p;//n个人m个关系p个查询 cinnmp; init(n);//初始化并查集 for(int i0;im;i){ int a,b; cinab; Union(a,b);//合并所有集合 } while(p--0){ int a,b; cinab; if(is_same_set(a,b)){//判断是否同一个集合就说明具有亲戚关系 coutYesendl; }else{ coutNoendl; } } return 0; }而我们在学生成绩管理系统里首先定义UnionFind类代码如下import java.util.*; public class UnionFind { private HashMapStudent, Student parent;//用于记录父节点 private HashMapStudent, Integer rank;//用于记录树的深度,有利于他的合并相当与模板里的Mysize[]; public UnionFind() { parent new HashMap(); rank new HashMap(); } public void addNode(Student s){//添加节点 if(!parent.containsKey(s)){//如果之前节点不存在则添加 parent.put(s, s);//父节点设为自己相当于模板里的parent[x] x; rank.put(s, 1);//树的深度设为1相当于模板里的Mysize[x] 1; } } public Student find(Student s){//查询节点,这里是递归写法 if(parent.get(s) ! s){ parent.put(s, find(parent.get(s))); } return parent.get(s); } public void union(Student s1, Student s2){//合并节点 Student p1 find(s1); Student p2 find(s2); if(p1 ! p2){ if(rank.get(p1) rank.get(p2)){ rank.put(p1, rank.get(p1) rank.get(p2)); parent.put(p2, p1); } else { rank.put(p2, rank.get(p1) rank.get(p2)); parent.put(p1, p2); } } } public boolean isSameSet(Student s1, Student s2){//判断两个节点是否属于同一个集合 return find(s1) find(s2); } }和前面的模板思路相同就是加入学生类和哈希表在测试类里面我们就使用它private static UnionFind uf new UnionFind();//先创建对象作为全局变量方法里的应用public static void addStudent(Student s) throws Exception { synchronized (lock) {//因为我同时用了多线程 String id s.getId(); if (map.containsKey(id)) throw new Exception(学号已存在); map.put(id, s); uf.addNode(s); String comb getCombination(s);//此方法是用于返会所选的几门科目312 /*public static String getCombination(Student s) { return s.getFirstSubject() , s.getSecondSubject1() , s.getSecondSubject2(); }*/ for (Student s1 : map.values()) {//相同组合里的合并到同一个集合里 if (!s1.getId().equals(id) getCombination(s1).equals(comb)) { uf.union(s, s1); break; } } } } //判断学生是否在同已选科目里 public static boolean isSameGroup(String id1, String id2){ Student s1 map.get(id1); Student s2 map.get(id2); if(s1 null || s2 null){ return false; } return uf.isSameSet(s1, s2); } //统计同组合的人数 public static void statGroupSimple() { MapStudent, Integer groupCount new HashMap();//用哈希表类记录个数 for (Student s : map.values()) { Student root uf.find(s); groupCount.put(root, groupcount.getOrDefault(root, 0) 1);//这是简写和以下是一样的 /* if(groupCount.containsKey(root)){ int countgroupCount.get(root); groupCount.put(root,count1); }else{ groupCount.put(root,1); }*/ } System.out.println(选科组合总种类 groupCount.size()); int i 1; for (Student root : groupCount.keySet()) { String combo getCombination(root); int people groupCount.get(root); out.println(第 i 种 组合 combo 人数 people);//一般都用PrintWriter来输出 i; } } //查询同选科的学生用其中一人的学号 public static void showSameGroup(String id) { // 根据学号找学生 Student target map.get(id); if (target null) { out.println(该学号不存在); return; } // 找这个学生根节点 Student root uf.find(target); out.println( 同选科所有同学 ); // 遍历所有学生根节点一样就是同选科 for (Student s : map.values()) { if (uf.find(s) root) { out.println(学号 s.getId() 姓名 s.getName()); } } } //同样的删除也是一个道理 public static void DeleteSameGroup(String id) { // 根据学号找目标学生 Student target map.get(id); if (target null) {//注意要判断一下 System.out.println(学号不存在无法删除); return; } // 找到这个选科组的根节点 Student root uf.find(target); // 先收集要删除的所有学号 ArrayListString deleteList new ArrayList(); for (Student s : map.values()) { if (uf.find(s) root) {//用find方法去找同一集合的学生 deleteList.add(s.getId()); } for (String id : deleteList) { map.remove(id);//通过学号来删除 } }简单总结一下我在写这个管理系统的时候并查集确实是一时想到的使用过程中也改过多次总的来说应用得很浅很浅比起大难的一些算法题来说应用的很浅了力扣情侣牵手逻辑思维上比这个更深以及好多不会写的题目不过这也是我的一个创新吧我也在慢慢实现它其实我对并查集的使用可能解释这个水平了还有好多应用我还没想到的希望大佬们多给建议我的提升空间很大算法的熟练是刷题和应用出来的就好像我听来做左神的课都懂了不写题那就白学了没啥更多好说的加油
