解题思路: 并查集(一种树型的数据结构)的运用,用于处理一些不相交的集合之间的合并与查询问题;
注意事项: 用cin,cout会超时,所以数据量较大的时候,尽量用scanf,printf;
参考代码:
#include <iostream> using namespace std; #define N 100001 int father[N]; void Init(int n) { for(int i=1;i<=n;i++) { father[i]=i; } } int Find(int x) { if(x==father[x]) return x; else return father[x]=Find(father[x]);//路径压缩 } void Union(int a,int b) { int roota=Find(a);//节点a int rootb=Find(b);//节点b if(roota!=rootb) { father[roota]=rootb; } } int main() { int n,m,k,a,b; cin>>n>>m>>k; Init(n); while(m--) { scanf("%d%d",&a,&b); Union(a,b); } while(k--) { scanf("%d%d",&a,&b); if(Find(a)==Find(b)) printf("Yes\n"); else printf("No\n"); } return 0; }//dongdong
0.0分
1 人评分
校门外的树 (C语言代码)浏览:961 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:703 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:576 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:863 |
蛇行矩阵 (C语言代码)浏览:536 |
愚蠢的摄影师 (C++代码)浏览:938 |
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:575 |
大神老白 (C语言代码)浏览:601 |
字符串比较 (C语言代码)浏览:685 |
数组输出 (C语言代码)浏览:703 |