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;

}