UVALive 6906 Cluster Analysis 并查集

唐伯虎

Cluster Analysis

题目连接：
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4918

Description
Cluster analysis, or also known as clustering, is a task to group a set of objects into one or more groups
such that objects belong to a same group are more similar compared to object in other groups. In this
problem, you are given a set of N positive integers and an integer K. Your task is to compute how
many clusters are there in the given set where two integers belong to a same cluster if their difference
is no larger than K.
For example, let there be a set of N = 7 positive integers: 2, 6, 1, 7, 3, 4, 9, and K = 1.
Based-on the cluster definition of K, we know that:
· 2 and 1 belong to a same cluster (the difference is no more than K = 1),
· 2 and 3 belong to a same cluster,
· 6 and 7 belong to a same cluster,
· 3 and 4 belong to a same cluster.
From these observations, we can conclude that there are 3 clusters in this example: {2, 1, 3, 4}, {6,
7}, and {9}.
Figure 1.
Figure 1 illustrates the clustering result. A line connecting two numbers means that those two
numbers should belong to a same cluster according to the definition.

Input
The first line of input contains an integer T (T ≤ 100) denoting the number of cases. Each case begins
with two integers in a line: N and K (1 ≤ N ≤ 100; 1 ≤ K ≤ 1, 000, 000) denoting the set size and
the clustering parameter respectively. The next line contains N integers Ai (1 ≤ Ai ≤ 1, 000, 000)
representing the set of positive integers. You are guaranteed that all integers in the set are unique

Output
For each case, output ‘Case #X: Y ’, where X is the case number starts from 1 and Y is the number
of cluster for that particular case.
Explanation for 2nd sample case:
The given set is exactly the same as in 1st sample, however, now K = 2. With two additional
observations (compared to 1st sample): 4 and 6 are in the same cluster, 7 and 9 are in the same cluster;
all those integers will be in the same cluster.
Explanation for 3rd sample case:
There are 2 clusters: {1, 4}, and {15, 20, 17}.
Explanation for 4th sample case:
In this sample, all integers will be in their own cluster.

Sample Input
4
7 1
2 6 1 7 3 4 9
7 2
2 6 1 7 3 4 9
5 5
15 1 20 4 17
8 10
100 200 300 400 500 600 700 800

Sample Output
Case #1: 3
Case #2: 1
Case #3: 2
Case #4: 8

Hint

题意
有n个数，如果两个数相差小于等于k的话，就可以属于一个集合，问你这n个数，可以属于多少个集合。

题解：
数据范围很小，直接暴力枚举，然后并茶几维护就好了

代码

#include <bits/stdc++.h>
#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define pb push_back
#define mp make_pair
#define sf scanf
#define pf printf
#define two(x) (1<<(x))
#define clr(x,y) memset((x),(y),sizeof((x)))
#define dbg(x) cout << #x << "=" << x << endl;
#define lowbit(x) ((x)&(-x))
const int mod = 1e9 + 7;
int mul(int x,int y){return 1LL*x*y%mod;}
int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
using namespace std;
const int maxn = 100 + 15;
int a[maxn],N,K,fa[maxn];


int find_set( int x ){
  return x != fa[x] ? fa[x] = find_set( fa[x] ) : x;
}

void Uuion_set( int x , int y ){
int p1 = find_set( x ) , p2 = find_set( y );
if( p1 != p2 ) fa[p1] = p2;
}

int main(int argc,char *argv[]){
int T=read(),cas=0;
while(T--){
N=read(),K=read();
rep(i,1,N) a[i]=read(),fa[i]=i;
rep(i,1,N) rep(j,1,N) if(i != j && abs( a[i] - a[j] ) <= K) Uuion_set( i , j );
set < int > sp;
rep(i,1,N) sp.insert(find_set(i));
pf("Case #%d: %d\n" , ++ cas , sp.size());
}
return 0;
}