企业官网建设流程全解析

在最近的学习中，我对并查集学得一般，懂其原理，但用得不深，不过在最近Java的期末项目里，我的主题是高考模式下的学生成绩管理系统，我的思考就停留在了新高考的3+1+2的选科目上，那是不是同组合的人要放在一块呢？结合我最近学过的知识，并差集刚好可以写它，也许这有点小题大做，但我就得自己学的好不好，还是实践才知道，具体说明如下：

引用洛谷P1551

# P1551 亲戚

## 题目描述

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x，y 是亲戚，那么 x 的亲戚都是 y 的亲戚，y的亲戚也都是 x 的亲戚。

## 输入格式

第一行：三个整数 n,m,p,(n,m,p <=5000），分别表示有 n 个人，m个亲戚关系，询问 p 对亲戚关系。

以下 m行：每行两个数 M_i，M_j，1 <= M_i,M_j< n，表示 M_i 和 M_j具有亲戚关系。

接下来 p行：每行两个数 P_i,P_j，询问 P_i 和 P_j 是否具有亲戚关系。

## 输出格式

p 行，每行一个 `Yes` 或 `No`。表示第 i个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例

输入 #1
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

输出 #1
Yes
Yes
No

很显然，这是一个模板题，要实现简单的并查集，代码如下：

#include <bits/stdc++.h> using namespace std; const int N=100010; int parent[N];//表示它的父节点 int Mysize[N];//表示他的长度，即根结点以下挂的长度 int Mystack[N];//提供一个空间去临时存他的状态 void init(int n) { for (int i=1;i<=n;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 size=0; while (n!=parent[n]) { Mystack[size++]=n;//压入栈中,收入不是根节点的节点 n=parent[n];//找父节点,就是让n向上指，直到找到跟节点 } while ( size>0) { parent[Mystack[--size]]=n;//弹出栈，将所有节点都指向根节点 } return n;//返回根节点 } void Union(int x,int y) {//合并两个集合 //首先去找他的根节点 int fx=find(x); int fy=find(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个查询 cin>>n>>m>>p; init(n);//初始化并查集 for(int i=0;i<m;i++){ int a,b; cin>>a>>b; Union(a,b);//合并所有集合 } while(p-->0){ int a,b; cin>>a>>b; if(is_same_set(a,b)){//判断是否同一个集合，就说明具有亲戚关系 cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } } return 0; }

而我们在学生成绩管理系统里，首先定义UnionFind类，代码如下：

import java.util.*; public class UnionFind { private HashMap<Student, Student> parent;//用于记录父节点 private HashMap<Student, 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);//此方法是用于返会所选的几门科目（3+1+2） /*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() { Map<Student, 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 count=groupCount.get(root); groupCount.put(root,count+1); }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); // 先收集要删除的所有学号 ArrayList<String> 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);//通过学号来删除 } }

简单总结一下，我在写这个管理系统的时候，并查集确实是一时想到的，使用过程中也改过多次，总的来说，应用得很浅很浅，比起大难的一些算法题来说应用的很浅了，力扣情侣牵手，逻辑思维上比这个更深，以及好多不会写的题目，不过这也是我的一个创新吧，我也在慢慢实现它，其实我对并查集的使用可能解释这个水平了，还有好多应用我还没想到的，希望大佬们多给建议，我的提升空间很大，算法的熟练是刷题和应用出来的，就好像我听来做左神的课，都懂了，不写题，那就白学了，没啥更多好说的，加油！