九度:http://ac.jobdu.com/problem.php?pid=1526
题目描述:
假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。
假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。
输入:
输入包含多个测试用例,每个测试用例的第一行包含两个正整数 n、m,1=<n,m<=100000。接下来有m行,每行分别输入两个人的编号f,t(1=<f,t<=n),表示f和t是好友。 当n为0时,输入结束,该用例不被处理。
输出:
对应每个测试用例,输出在这n个人里一共有多少个朋友圈。
样例输入:
5 3
1 2
2 3
4 5
3 3
1 2
1 3
2 3
0
样例输出:
2
1
#include <stdio.h>
int n, m, f[100001],i;
int findSet(int x) {
int t = x;
while (f[x] > 0)
x = f[x];
while (t != x) { //路径压缩
int q = f[t];
f[t] = x;
t = q;
}
return x;
}
void unionSet(int x, int y) {
int fx = findSet(x);
int fy = findSet(y);
if (fx != fy) {
n--;
int tmp = f[fx] + f[fy];//两个集合个数之和
if (f[fx] < f[fy]) { //大集合 吞并小集合.
f[fy] = fx;
f[fx] = tmp;
} else {
f[fx] = fy;
f[fy] = tmp;
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
int a,b;
while(scanf("%d",&n), n) {
scanf("%d", &m);
for( i=1; i<=n; i++)
f[i] = -1;
for(i=0; i<m; i++) {
scanf("%d %d", &a,&b);
unionSet(a,b);
}
printf("%d\n", n);
}
return 0;
}
分享到:
相关推荐
京东 校园招聘笔试试题--软件开发笔试题 -.docx京东 校园招聘笔试试题--软件开发笔试题 -.docx京东 校园招聘笔试试题--软件开发笔试题 -.docx京东 校园招聘笔试试题--软件开发笔试题 -.docx京东 校园招聘笔试试题--...
奥克斯集团2013年校园招聘笔试题-硬件类试题
奥克斯集团2013年校园招聘笔试题-制冷(系统)类试题
奥克斯集团2013年校园招聘笔试题-管理类试题
奥克斯集团2013年校园招聘笔试题-软件类试题
百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习...
百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园...
奥克斯 2013年校园 招聘 笔试题 财务类 试题
百度校园招聘笔试面试题22个文档资料合集: 百度2010-2011年各部门招聘笔试题及面经总结.doc 百度2014校园招聘笔试试题-产品经理笔试题.doc 百度2014校园招聘笔试试题-北京站未知岗位.docx 百度2014校园招聘笔试试题...
基恩士2013校园招聘笔试题-销售
携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园...
2013年阿里巴巴校园招聘笔试试题研发工程师.doc 2014年3月阿里巴巴实习招聘笔试题及部分答案.docx 2014年阿里巴巴校园招聘笔试题杭州站-研发类.doc 淘宝2011实习招聘笔试.doc 淘宝校园招聘清华笔试试题.doc 淘宝校园...
百度2014校园招聘笔试试题-研发工程师笔试题.docx
奇虎360 2013校园招聘笔试试题-技术类-高清无答案.docx
奇虎360 2013校园招聘笔试试题-产品类-华中科技大学.doc
奇虎360 2013校园招聘笔试试题-产品类-华中科技大学.pdf
2013去哪儿网校园招聘笔试试题--技术类.docx