并查集

知乎上一个大佬写的拉帮结派版并收集:算法学习笔记

总结一下我的收获

1. 初始化：各自成帮派，父节点就是你自己

int fa[N]; void init(){ 
          for(int i=0;i<N;i ){ 
           fa[i] = i;  } } 

2. 查：递归找帮主，一层一层地搜索到根节点，如果两个节点的根节点相同，则是同一帮派

void find(int i){ 
          if(fa[i] == i) return fa[i];  return find(fa[i]); } 

3. 合并:两帮主决斗后，选择两帮主后两帮的合并，即一个集合中所有元素改变其根节点

void unionn(int i,int j){ 
          fa[find(i)] = find(j); ///将i合并到j的集合中，直接将i原根节点的父节点改为j根节点 } 

缺点:每次要合并的帮派帮主比原帮派帮主强，整个树形集合最终会变成长链表，效率太低

沿途所有节点将树中的根节点叶节点父节点设置为根节点，最后形成菊花形(最大深度为2)的树形结构 改变上述的 查 代码：

void find(int i){ 
          if(fa[i] == i) return fa[i];  else{ 
           fa[i] = find(fa[i]); //将i的父节点设置为根节点
		return fa[i];
	}
}

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 Input 第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。 以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。 接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。 Output P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。 Sample Input

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

Sample Output

Yes
Yes
No

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int fa[N];
void init(int n){ 
        
	for(int i=1;i<=n;i++){ 
        
		fa[i] = i;
	} 
		
}
int find(int x){ 
        
	if(x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
void unionn(int i,int j){ 
        
	int i_fa = find(i);
	int j_fa = find(j);
	//将 i 的根节点的父节点设为 j 的 根节点 
	fa[i_fa] = j_fa; 
}
int main(){ 
        
	int n,m,p,a,b;	
	scanf("%d %d %d",&n,&m,&p);
	init(n);
	for(int i=0;i<m;i++){ 
        
		scanf("%d %d",&a,&b);
		unionn(a,b);
	}
	for(int i=0;i<p;i++){ 
        
		scanf("%d %d",&a,&b);
		if(find(a) == find(b)){ 
        
			cout << "Yes\n";
		} 
		else cout << "No\n";
	}
	return 0;
}

小蓝要用七段码数码管来表示一种特殊的文字。

上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二 极管，分别标记为 a, b, c, d, e, f, g。 小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。 例如：b 发光，其他二极管不发光可以用来表达一种字符。 例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。 例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。 请问，小蓝可以用七段码数码管表达多少种不同的字符？

参考的这位大佬的博客：[蓝桥杯2020] E题.七段码 //dfs+并查集

1. 把abcdefg转为数字1234567，以便并查集初始化

得到总共10组相连的边

1 2
1 6
2 7
2 3
3 4
3 7
4 5
5 7
5 6
6 7

2. 用dfs()遍历，每个灯都有亮和没亮两种状态
3. dfs遍历时，先将每两个亮着并且相连（用连通图储存）的灯合并到一起，最后再检查该种方法是否只包含一个集合。

自己又写了一遍