UVALive 6906 Cluster Analysis 并查集

题目地址：见这里 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

题意就是：有n个数，如果两个数相差小于等于k的话，就可以属于一个集合，问你这n个数，可以属于多少个集合。 解法：数据小，直接暴力枚举+dsu维护

//LA 6906 #include <bits/stdc++.h> using namespace std; const int maxn = 115; int a[maxn], n, k; namespace dsu{ int fa[maxn]; inline void init(){for(int i = 1; i <= n; i++) fa[i] = i; } inline int find_set(int x){if(x == fa[x]) return x; else return fa[x] = find_set(fa[x]);} inline void union_set(int x, int y){x = find_set(x), y = find_set(y); if(x != y) fa[x] = y;} } using namespace dsu; int main() { int T, ks = 0; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); init(); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(i != j && abs(a[i] - a[j]) <= k) union_set(i, j); } } set <int> s; for(int i = 1; i <= n; i++) s.insert(find_set(i)); printf("Case #%d: %d\n", ++ks, s.size()); } return 0; }