首页 > 代码库 > kuangbin专题五、并查集
kuangbin专题五、并查集
题意:给你1~n的点的坐标,O x,表示x点修好,S x y表示查询x点能否连通y点,连通的条件是dis<d
直接判断最后查询时,是否在同一个集合就可以。
ps:注意两点是否在同一集合,必须用find()找,因为fa[]找的,可能不是最终的爸爸。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 int n,d; 6 int x[1005],y[1005]; 7 int vis[1005],fa[1005]; 8 9 bool ind(int a,int b) 10 { 11 return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])<=d*d; 12 } 13 int find(int x) 14 { 15 if(fa[x]!=x) fa[x]=find(fa[x]); 16 return fa[x]; 17 } 18 void unin(int a,int b) 19 { 20 int x=find(a); 21 int y=find(b); 22 if(x!=y) fa[x]=y; 23 return; 24 } 25 int main() 26 { 27 while(~scanf("%d%d",&n,&d)) 28 { 29 for(int i=1;i<=n;i++) 30 { 31 scanf("%d%d",&x[i],&y[i]); 32 fa[i]=i; 33 vis[i]=0; 34 } 35 char s[2]; 36 int a,b; 37 while(scanf("%c",&s)!=EOF) 38 { 39 if(s[0]==‘O‘) 40 { 41 scanf("%d",&a); 42 vis[a]=1; 43 for(int i=1;i<=n;i++) 44 if(vis[i] && ind(a,i) && i!=a) 45 unin(i,a); 46 } 47 if(s[0]==‘S‘) 48 { 49 scanf("%d%d",&a,&b); 50 if(find(a)==find(b)) puts("SUCCESS"); 51 else puts("FAIL"); 52 } 53 } 54 } 55 return 0; 56 }
kuangbin专题五、并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。