湘西州建设银行网站,技术支持 中山网站建设,网站建设分金手指专业十四,苏州seo网站推广公司并查集可以理解为数学上的集合
并查集一般以树这种数据结构来储存每一个元素#xff0c;判断两个元素是否为同一个集合#xff0c;通常判断两个元素所在的树的根结点是否相同#xff0c;因为比较两个元素是否是同一个树要向上查找根结点#xff0c;所以一般用双亲表示法判断两个元素是否为同一个集合通常判断两个元素所在的树的根结点是否相同因为比较两个元素是否是同一个树要向上查找根结点所以一般用双亲表示法储存在数组中
并查集的两种操作
1.查找某个元素所在的集合
并查集中集合一般以根结点表示所以查找集合等价于找根结点
//a数组表示集合a[i]表示下标为i的元素的父结点所在的位置
int find(int x)
{if(a[x]0)//根结点没有父亲元素值为0return x;else{a[x]find(a[x]);//压缩路径return a[x]
}
2.合并两个元素所在的集合
void bing(int left, int right)//传入要合并的两个元素
{int t1 find(left);//找到根结点int t2 find(right);//找到根结点if (t1 ! t2)//如果两个元素不在同一个集合{s[t2] t1;//将其中一个根结点的父结点指向另一个}return;
}
洛谷 P3367 【模板】并查集
题目描述
如题现在有一个并查集你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来 M 行每行包含三个整数 Zi,Xi,Yi 。
当 Zi1 时将 Xi 与 Yi 所在的集合合并。
当 Zi2 时输出 Xi 与 Yi 是否在同一集合内是的输出 Y 否则输出 N 。
输出格式
对于每一个 Zi2 的操作都有一行输出每行包含一个大写字母为 Y 或者 N 。
输入输出样例
输入 #1
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出 #1
N
Y
N
Y说明/提示
对于 30% 的数据N≤10M≤20。
对于70% 的数据N≤100M≤10^3。
对于 100% 的数据1≤N≤10^41≤M≤2×10^51≤Xi,Yi≤NZi∈{1,2}。
模板题考察的就是并查集的两种操作
AC代码
#includestdio.h
int a[10001], n, m, flag;
int find(int x)//传入要查找的元素返回其集合的根结点
{if (a[x] 0)//根结点的父结点指向0遇到0结束return x;else//若父结点不是根结点让值本身等于其父亲查找父亲的父结点是否为根结点{a[x] find(a[x]);//压缩路径return a[x];}
}
void bing(int x, int y, int z)//
{int t1 find(x);//找到x集合根结点int t2 find(y);//找到y集合根结点if (t1 ! t2)//两个元素不在同一个集合{if (z 1)//z为1合并两个集合a[t2] t1;if (z 2)//z为2且两个元素不在同一个集合输出Nprintf(N\n);return;}else if (z 2)//两个元素在同一个集合且z等于2输出Yprintf(Y\n);return;
}
int main()
{int x, y, z;scanf(%d %d, n, m);while (m--){scanf(%d %d %d, z, x, y);bing(x, y, z);}return 0;
}洛谷 P1111 修复公路
题目背景
A 地区在地震过后连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述
给出 A 地区的村庄数 N和公路数 M公路是双向的。并告诉你每条公路的连着哪两个村庄并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车即最早什么时候任意两条村庄都存在至少一条修复完成的道路可以由多条公路连成一条道路。
输入格式
第 1 行两个正整数 N,M。
下面 M 行每行 3 个正整数x,y,t告诉你这条公路连着 x,y 两个村庄在时间t时能修复完成这条公路。
输出格式
如果全部公路修复完毕仍然存在两个村庄无法通车则输出 −1否则输出最早什么时候任意两个村庄能够通车。
输入输出样例
输入 #1
4 4
1 2 6
1 3 4
1 4 5
4 2 3
输出 #1
5
说明/提示
1≤x,y≤N≤10^31≤M,t≤10^5。 解题思路
本题也是考察并查集的两个操作特殊的是如何判断修完后任意两个村庄是否通车和最短在什么时候任意两个点能通车
第一点很好判断在所有路修完后是否只有一个根结点如果只有一个根结点即任意两点能通车
要满足第二点首先要根据修每条路的时间进行从小到大排序之所以要排序是因为两个村庄如果第一次有连系就会优先更新最小时间。
特殊的两点思路已知看代码
#includestdio.h
struct nm {//结构体储存修的每一条路的信息int le, ri;int tt;
}a[100010], b[100010], t;
void nm(int x, int y)//归并排序更据修路时间从小到大排序不用多少
{if (x y) return;int mid (x y) / 2;nm(x, mid);nm(mid 1, y);int k 1;int i x, j mid 1;while (i mid j y){if (a[i].tt a[j].tt)b[k] a[i];elseb[k] a[j];}while (i mid)b[k] a[i];while (j y)b[k] a[j];for (i 1; i k; i)a[x i - 1] b[i];
}
int s[1010], book[1010], flag;
int getf(int x)//查找x元素根结点
{if (s[x] 0)return x;else{s[x] getf(s[x]);//压缩路径return s[x];}
}
int bing(int left, int right)//返回1代表两个元素不在同一集合返回0代表在同一集合
{//得到两个元素的根结点int t1 getf(left);int t2 getf(right);if (t1 ! t2)//两个元素不在同一集合{s[t2] t1;//合并return 1;}return 0;
}
int main()
{int n, m, i, t 0;scanf(%d %d, n, m);int sum n;//初始有n个集合for (i 1; i m; i)scanf(%d %d %d, a[i].le, a[i].ri, a[i].tt);nm(1, m);//排序for (i 1; i m; i)//修m条路{int ss bing(a[i].le, a[i].ri);//合并if (ss 1)//如果ss为1代表两个村庄所在的集合第一次有连系{sum--;//两个集合合并树的数量减少1t a[i].tt;//更新时间}}if (sum 1)//如果只有唯一集合即所有村庄都有联系printf(%d, t);else//存在两个村庄无法通车输出 −1printf(-1);return 0;
}
