参考文章：https://www.jianshu.com/p/89cea54d3f22
并查集介绍
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
主要操作：初始化、查找、合并
下面是我的代码：
//并查集实现
public class bingchajiDemo {
static int[] par = new int[6]; // 父亲
static int[] rank = new int[6]; //树的高度
// 初始化n个元素
public static void init(int n){
for(int i=1 ; i <= n ; i++){
par[i] = i;
rank[0] = 0;
}
}
// 查询树的根
public static int find(int x){
if(par[x] == x){
return x;
}else{
par[x] = find(par[x]);
return par[x];
}
}
//合并x和y所属的集合
public static void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y){
return;
}
if (rank[x] < rank[y]){
par[x] = y;
}else{
par[y] = x;
if(rank[x] == rank[y]){
rank[x] ++;
}
}
}
//判断x y是不是在同一个集合
public static boolean same(int x, int y){
return find(x) == find(y);
}
public static void main(String[] args) {
init(5);
System.out.println(find(2));
}
}
算法训练
https://www.cnblogs.com/attacking-vincent/p/13154731.html
食物链
//并查集实现
public class bingchajiDemo {
static int[] par = new int[3*150010]; // 父亲
static int[] rank = new int[3*150010]; //树的高度
// 初始化n个元素
public static void init(int n){
for(int i=1 ; i <= n ; i++){
par[i] = i;
rank[0] = 0;
}
}
// 查询树的根
public static int find(int x){
if(par[x] == x){
return x;
}else{
par[x] = find(par[x]);
return par[x];
}
}
//合并x和y所属的集合
public static void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y){
return;
}
if (rank[x] < rank[y]){
par[x] = y;
}else{
par[y] = x;
if(rank[x] == rank[y]){
rank[x] ++;
}
}
}
//判断x y是不是在同一个集合
public static boolean same(int x, int y){
return find(x) == find(y);
}
// 解决
public static void solve(int n,int k,int[] T,int[] X,int[] Y){
init(n*3);
int ans = 0;
for (int i=0 ;i<k ;i++){
int t = T[i];
int x = X[i]-1;
int y = Y[i]-1;
// 不正确编号
if(x<0||n<=x||y<0||n<=y){
ans++;
continue;
}
if(t==1){
if(same(x,y+n)||same(x,y+2*n)){
ans ++;
}else{
unite(x,y);
unite(x+n,y+n);
unite(x+2*n,y+2*n);
}
}else{
if(same(x,y)||same(x,y+2*n)){
ans++;
}else{
unite(x,y+n);
unite(x+n,y+2*n);
unite(x+2*n,y);
}
}
}
System.out.println("ans:"+ans);
}
public static void main(String[] args) {
int n = 100;
int k = 7;
int[] T = {1,2,2,2,1,2,1};
int[] X = {101,1,2,3,1,3,5};
int[] Y = {1,2,3,3,3,1,5};
solve(n,k,T,X,Y);
}
}
