UVA10608 Friends

题目描述

某个小镇里有 个位公民，其中有些人是朋友关系。

在这个小镇里，“我的朋友的朋友是我的朋友”是一条不变的真理，即如果 和 是朋友， 和 是朋友，那么 和 也是朋友。

由于镇里的朋友太多，形成了几个朋友团（在任何一个朋友团里的人都是朋友，而任意两个不相同朋友团的人不是朋友）。你想知道镇里最大的朋友团里有多少位公民。

输入格式

本题有多组数据。

第一行一个正整数 ，代表数据组数，保证为 int 范围。

接下来对于每一组数据：

第一行两个数 和 ， 代表公民数， 代表朋友的对数。

接下来 行，每行两个整数 和 ，代表居民 和居民 是朋友。保证 和 均小于 且不相等，但可能会出现重复的数据。

输出格式

对于每组数据，输出一行一个整数，代表镇里最大的朋友团里的公民数量。

输入输出样例 #1

输入 #1

2
3 2
1 2
2 3
10 12
1 2
3 1
3 4
5 4
3 5
4 6
5 2
2 1
7 1
1 2
9 10
8 9

输出 #1

3
7

说明/提示

，。

题解

观察题目

“你的朋友也是我的朋友”这条规则就决定了，这是一个“社区发现问题”，那么用并查集是最方便的解法。

不过这里求的是“最大朋友圈的规模”，那我们可以维持一个 sizes【N】 数组，初始值为 1，表示 N 个居民分为 N 个圈子，每个圈子的规模都是 1。每当 x 和 y 两个圈子合并时，x 圈子归入 y 圈子，则 sizes[y]+=sizes[x]表示 y 圈子吸纳 x 圈子后的规模，sizes[x]则表示 x 圈子消失。

代码

#include<iostream>
#include<string.h>
using namespace std;

const int max_size=3e4+5;
int N,M;
int Max_one;
int set[max_size]={};
int sizes[max_size]={};

int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x;
}

void init(){
    Max_one=0;
    for(int i=1;i<=N;i++){
        set[i]=i;
        sizes[i]=1;
    } 
}

int find_set(int x){
    if(x!=set[x]){
        set[x]=find_set(set[x]);
    }
    return set[x];
}
void merge_set(int x,int y){
    x=find_set(x);y=find_set(y);
    if(x!=y){
        set[x]=y;
        sizes[y]+=sizes[x];
        sizes[x]=0;
        Max_one=Max_one>=sizes[y]?Max_one:sizes[y];
    }
}
void f(){
    N=read();M=read();
    init();
    int x,y;
    for(int i=0;i<M;i++){
        x=read();y=read();
        merge_set(x,y);
    }
    printf("%d\n",Max_one);
}

int main(){
    int T=read();
    while(T--) f();
    return 0;
}