1010 朋友圈【小米2013年校园招聘笔试题】-爱上极客

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

2014-10-05 分类：数据结构与算法 loading.. 评论(1)

进入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

并查集