上课笔记
2024-08-31 17:00:33
发布于:广东
笔记:
并查集
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 5e3 + 9;
int fa[maxn];//存父节点
//传入编号为x的节点
int get(int x){
if(fa[x] == x){
return x;//自己就是自己
}
return get(fa[x]);//接着搜索集合中 父节点;
}
void merge(int x,int y){//x,y不认识的节点合并
fa[get(x)]=get(y);//fa[get(y] = get(x);
}
int main(){
int n, m , p;scanf("%d %d %d",&n,&m,&p);
for(int i=1;i<=n;i++)fa[i] = i;//自己就是自己
for(int i=1;i<=m;i++){
int u , v;scanf("%d %d"i,&u,&v);//建造顶点u,v
if(get(u) != get(v)){//u,v彼此不认识
merge(u, v);//两个人认识了,u认识v,v也认识u
}
}
//进行p次询问
while(p--){
int x,y;scanf("%d %d",&x,&y);
//get(x):返回的是x所在集合中的代表
//get(y):返回的是y所在集合中的代表
if(get(x)==get(y))printf("Yes\n");
else printf("No\n");
}
return 0;
}
/*
拓扑排序:
并查集: 图分为若干个不相交的“集合”-数据结构
用于 - 处理不相交集合的合并与查询
由不相交的集合中,每个集合通过代表(represent)来区分,
代表是集合中的某个成员
*/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 3e4 + 9;
int fa[maxn];//存父节点
//传入编号为x的节点
int get(int x){
if(fa[x] == x){
return x;//自己就是自己
}
return fa[x]=get(fa[x]);//接着搜索集合中 父节点;
}
void merge(int x,int y){//x,y不认识的节点合并
fa[get(x)]=get(y);//fa[get(y] = get(x);
}
int main(){
int n, m ;scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)fa[i] = i;//自己就是自己
for(int i=1;i<=m;i++){
int z,x,y;scanf("%d %d %d",&z,&x,&y);//建造顶点u,v
if(z==1){//u,v彼此不认识
if(get(x)!=get(y))
merge(x, y);//两个人认识了,u认识v,v也认识u
}else{
if(get(x)==get(y))printf("Y\n");
else printf("N\n");
}
}
return 0;
}
/*
拓扑排序:
并查集: 图分为若干个不相交的“集合”-数据结构
用于 - 处理不相交集合的合并与查询
由不相交的集合中,每个集合通过代表(represent)来区分,
代表是集合中的某个成员
*/
这里空空如也
有帮助,赞一个