九度题目1526:朋友圈-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

九度题目1526:朋友圈

简介:

 

题目1526:朋友圈
时间限制:1 秒
内存限制:128 兆
特殊判题:否
提交:934
解决:278
题目描述:
假如已知有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
来源:
小米2013年校园招聘笔试题

 


并查集
AC代码:

#include<stdio.h>
int a[100010];
int findx(int x)//用来找每个节点的根节点 
{
    if(a[x]!=x) 
    {
        a[x]=findx(a[x]);
    }
    return a[x];

}
void merge(int x,int y)
{
    int fx,fy;
    fx = findx(x);
    fy = findx(y);
    if(fx != fy)
        a[fx] = fy;
}//y并到x 里面
int main()
{
    int i,j,n,m,sum,x,y;
    while(scanf("%d",&n),n!=0)
    {
        scanf("%d",&m);
        for(i=1;i<=n;i++)
        a[i]=i;
        for(i=0;i<m;i++)
        {
            scanf("%d %d",&x,&y);
            merge(x,y);
        }
        sum=0;
        for(i=1;i<=n;i++)
        {
           if(a[i]==i)
           sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}


 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章