i3geek.com
闫庚哲的个人博客

1010 朋友圈【小米2013年校园招聘笔试题】

进入OJ

Description

假如已知有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个朋友圈。

Input

输入包含多个测试用例,每个测试用例的第一行包含两个正整数 n、m,1<=n,m<=100000。接下来有m行,每行分别输入两个人的编号f,t(1<=f,t<=n),表示f和t是好友。 当n为0时,输入结束,该用例不被处理。

Output

对应每个测试用例,输出在这n个人里一共有多少个朋友圈。

Sample Input

5 3
1 2
2 3
4 5
3 3
1 2
1 3
2 3
0

Sample Output

2
1

Hint

并查集:http://www.i3geek.com/?p=497

Source

小米2013年校园招聘笔试题

Code

#include <stdio.h>
unsigned int n,m;
int str[100011];

int find(int x)
{
    if(x != str[x])
        str[x]= find(str[x]);//压缩
    return str[x];
}
void uno(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx == fy) return;
    else
    {
        str[fx] = fy;//合并节点
        n--;
    }

}
int main() {
    while(scanf("%d", &n)!=EOF && n > 0) {
        scanf("%d", &m);
        for(int i=0;i<n;i++)
            str[i]=i;
        int a,b;
        while(m--)
        {
            scanf("%d %d", &a, &b);
            uno(a-1,b-1);
        }
        printf("%d\n",n);
    }
    return 0;
}

 Link

并查集

赞(0)
未经允许不得转载:爱上极客 » 1010 朋友圈【小米2013年校园招聘笔试题】
分享到: 更多 (0)

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    与众不同

    新青年摄影5年前 (2014-10-08)回复