脚本宝典收集整理的这篇文章主要介绍了并查集 --以cogs259为例,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
题目链接:http://cogs.pro:8081/cogs/problem/problem.php?pid=pySmxSVgP
【问题描述】
1 #define _CRT_SECURE_NO_WARNINGS 2 #include <iostream> 3 #include <cstdio> 4 #define MAXN 1000100 5 using namespace std; 6 7 int N,M,PRe[MAXN] = { 0 },Q; 8 int ai,bi; 9 10 int find(int x) 11 { 12 if (x == pre[x]) 13 return x; 14 return pre[x] = find(pre[x]); //路径压缩 15 } 16 17 void Union(int x,int y) 18 { 19 int xpre = find(x); 20 int yPre = find(y); 21 if (xPre != yPre) 22 pre[y] = xPre; 23 } 24 25 void preWork() 26 { 27 for (int i = 1; i <= N; i++) 28 pre[i] = i; 29 } 30 31 int main() 32 { 33 freoPEn("relations.in","r",stdin); 34 freopen("relations.out","w",stdout); 35 scanf("%d%d",&N,&M); 36 preWork(); 37 38 while (M--) 39 { 40 scanf("%d %d",&ai,&bi); 41 Union(ai,bi); 42 } 43 scanf("%d",&Q); 44 while (Q--) 45 { 46 scanf("%d %d",&bi); 47 int aPre = find(ai); 48 int bPre = find(bi); 49 if (aPre != bPre) 50 printf("No\n"); 51 else 52 printf("Yes\n"); 53 } 54 return 0; 55 }
以上是脚本宝典为你收集整理的并查集 --以cogs259为例全部内容,希望文章能够帮你解决并查集 --以cogs259为例所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。