本文共 1676 字,大约阅读时间需要 5 分钟。
简单并查集,只是注意输出的是x下边有多少元素
1、题目大意:
john 正在玩积木,有N个积木编号为1、、、N,分成N堆,每堆只包含一个积木,然后做P次操作,操作分为2种,
M X Y:把包含X的一堆放到包含Y的一堆上,如果XY同在一堆上,不做处理
C X:计算出X积木下边有多少个积木
每次遇到C操作,输出数量
2、题目:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1729 Accepted Submission(s): 516
6M 1 6C 1M 2 4M 2 6C 3C 4
102
3、代码:
#include#include int num[333333];int set[333333];int under[333333];int find(int x){ int tmp; if (x!=set[x]) { tmp = find(set[x]); under[x] += under[set[x]]; set[x] = tmp; } return set[x];}void merge(int a,int b){ int fx=find(a); int fy=find(b); if(fx!=fy) { under[fx]=num[fy]; num[fy]+=num[fx]; set[fx]=fy; }}int main(){ int n,a,b; char s[5]; while(scanf("%d",&n)!=EOF) { memset(under,0,sizeof(under)); for(int i=0; i<=n; i++)//初始化 { set[i]=i; num[i]=1; } for(int i=0; i
转载地址:http://ufcdi.baihongyu.com/