一群人相互交友。M 1 2 代表1和2成为朋友 Q 1 代表查询1的朋友数。
Sample Input
3 5
M 1 2
Q 1
Q 3
M 2 3
Q 2
5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4
Sample Output
Case 1:
2
1
3
Case 2:
1
1
3
1
4
思路:并查集问题。
#include<iostream>
using namespace std;
#include<memory.h>
#include<stdio.h>
int disjoinset[100001];
int find(int * s,int x)
{
if(s[x] <= 0)
return x;
else
return s[x] = find(s,s[x]); //path compress
}
void unionbysize(int *s,int root1,int root2)
{
if(s[root1] <= s[root2]) //root1 is bigger
{
s[root1] = s[root1] + s[root2];
s[root2] = root1;
}
else
{
s[root2] = s[root1] + s[root2];
s[root1] = root2;
}
}
//并查集内容 负数代表个数,正数代表父节点
int main()
{
int N;
int M;
char type;
int mem1;
int mem2;
int root1;
int root2;
int i = 0;
bool isfirst = true;
while(scanf("%d%d",&N,&M) != EOF)
{
memset(disjoinset,-1,100001*sizeof(int));
if(!isfirst)
printf("\n");
isfirst = false;
printf("Case %d:\n",++i);
while(M--)
{
getchar();
scanf("%c",&type);
if(type == 'M')
{
scanf("%d%d",&mem1,&mem2);
root1 = find(disjoinset,mem1);
root2 = find(disjoinset,mem2);
if(root1 != root2)
unionbysize(disjoinset,root1,root2);
}
else if(type == 'Q')
{
scanf("%d",&mem1);
root1 = find(disjoinset,mem1);
printf("%d\n",-disjoinset[root1]);
}
}
}
}
分享到:
相关推荐
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 3590 -3+1.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 3212 K-Nice.md
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
acm中zoj1002的可运行C++程序
zoj 2561 Order-Preserving Codes.md
包含了zoj700多道题目的源代码,在做题时可以参考
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
NULL 博文链接:https://weitch.iteye.com/blog/1006972
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够