PayPal上海团队一直致力于风险控制，风控需要收集各种信息，有时需要通过地理位置找出用户与用户之间存在的关联关系，这一信息可能会用于找出用户潜在存在的风险问题。我们记两个用户的关联关系可以表示为：
(1). user1，user2与他们最常发生交易的地理位置分别为(x1, y1)，(x2, y2)，当这两个用户的欧氏距离不超过d时，我们就认为两个用户关联。
(2). 用户关联性具有传递性，若用户1与用户2关联，用户2与用户3关联，那么用户1，2，3均关联。
给定N个用户及其地理位置坐标，将用户按照关联性进行划分，要求返回一个集合，集合中每个元素是属于同一个范围的用户群。
d:欧式距离
N:用户数
之后的N行表示第0个用户到第N-1个用户的地理位置坐标
一个数组集合，所有关联的用户在一个数组中。
输出数组需要按照从小到大的顺序排序，每个集合内的数组也需要按照从小到大的顺序排序。
2.0 5 3.0 5.0 6.0 13.0 2.0 6.0 7.0 12.0 0.0 2.0
[[0, 2], [1, 3], [4]]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
double d = Double.parseDouble(br.readLine().trim());
int n = Integer.parseInt(br.readLine().trim());
double[][] coordinate = new double[n][2];
String[] strArr;
for(int i = 0; i < n; i++){
strArr = br.readLine().trim().split(" ");
coordinate[i][0] = Double.parseDouble(strArr[0]);
coordinate[i][1] = Double.parseDouble(strArr[1]);
}
UnionFind uf = new UnionFind(n, d);
for(int i = 0; i < n - 1; i++){
for(int j = i + 1; j < n; j++){
// 节点i和j是连通的，进行合并
if(uf.isConnected(coordinate[i][0], coordinate[i][1], coordinate[j][0], coordinate[j][1]))
uf.union(i, j);
}
}
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
for(int i = 0; i < n; i++){
if(uf.parent[i] == i){
// 这是个根节点
ArrayList<Integer> userSet = new ArrayList<>();
// 寻找这个集合中的所有元素
for(int j = 0; j < n; j++)
if(uf.parent[j] == i) userSet.add(j);
res.add(new ArrayList<Integer>(userSet));
}
}
System.out.println(res);
}
}
class UnionFind {
public int[] parent;
private double d;
public UnionFind(int n, double d) {
parent = new int[n];
// 代表元法
for(int i = 0; i < n; i++)
parent[i] = i;
this.d = d;
}
// 判断节点(x1,y1)和(x2,y2)是否是关联的
public boolean isConnected(double x1, double y1, double x2, double y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= d * d;
}
// 获得节点i的所属集合(即根节点)
public int find(int x) {
while(x != parent[x]){
parent[x] = parent[parent[x]]; // 路径压缩
x = parent[x];
}
return x;
}
// 合并节点i和j
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
// 将节点编号大的合并到节点编号小的节点下面
if(rootX < rootY){
for(int i = 0; i < parent.length; ++i){
if(parent[i] == rootY)
parent[i] = rootX;
}
}else{
for(int i = 0; i < parent.length; ++i) {
if(parent[i] == rootX)
parent[i] = rootY;
}
}
}
} 使用并查集解决。详情：看这里。
这里贴一下代码。
//采用并查集思想，将所有的关联节点父子关系使用数组索引表示
import java.util.*;
public class Main{
static int[] users;
static double d; //欧式距离
//判断相连
private static boolean isConnected(double x1, double y1, double x2, double y2){
double dis = Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); //计算两点距离
return dis <= d;
}
//获取当前节点的根节点
private static int getRoot(int i){
return users[i];
}
//合并p、q，将q的根节点设置为q的根节点
private static void union(int p, int q){
int pRoot = getRoot(p);
int qRoot = getRoot(q);
if (pRoot < qRoot) {
for (int i = 0; i < users.length; ++i) {
if (users[i] == qRoot) {
users[i] = pRoot;
}
}
} else {
for (int i = 0; i < users.length; ++i) {
if (users[i] == pRoot) {
users[i] = qRoot;
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
d = sc.nextDouble();
int n = sc.nextInt();
users = new int[n];
for( int i=0; i<n; ++i ){
users[i] = i;
}
double[][] pos = new double[n][2];
//读取位置信息，存入二维数组
for( int i=0; i<n; ++i ){
pos[i][0] = sc.nextDouble();
pos[i][1] = sc.nextDouble();
}
//遍历数组，建立联系
for( int i=0; i<n; ++i ){
for( int j=0; j<i; ++j ){
if( isConnected(pos[i][0], pos[i][1], pos[j][0], pos[j][1]) ) {
union(i, j);
}
}
}
//将有联系的用户放进集合
ArrayList> res = new ArrayList();
for( int i=0; i<n; ++i ){
if( users[i] == i ){
//如果这是一个根节点，建立一个关于她的数组集合
ArrayList temp = new ArrayList();
for( int j=i; j<n; ++j ){
if( users[j]==i ) temp.add(j);
}
res.add(temp);
}
}
System.out.println(res);
}
}
用并查集解决该问题，未进行路径压缩。
public static void main(String[] args) {
Contest_137 tContest_137 = new Contest_137();
Scanner sc = new Scanner(System.in);
double d = 0;
int N = 0;
d = sc.nextDouble();
N = sc.nextInt();
double[][] point = new double[N][2];
for(int i = 0;i < N;i++){
point[i][0] = sc.nextDouble();
point[i][1] = sc.nextDouble();
}
tContest_137.func(N,point,d);
}
public void func(int N,double[][] point,double d) {
int[]data2 = new int[N];
for(int i = 0;i < data2.length;i++)
data2[i] = i;
double[][] distance = new double[N][N];
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
distance[i][j] = dis(point,i,j);
}
}
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
if(i != j) {
if(Math.sqrt(distance[i][j]) <= d){
union(data2,i,j);
}
}
}
}
TreeMap<Integer, TreeSet<Integer>> map = new TreeMap<Integer, TreeSet<Integer>>();
for(int i = 0;i < data2.length;i++) {
int k = find(data2,i);
TreeSet<Integer> set = map.getOrDefault(k, new TreeSet<Integer>());
set.add(i);
map.put(k, set);
}
StringBuilder res = new StringBuilder("[");
for(Map.Entry<Integer, TreeSet<Integer>> entry : map.entrySet()) {
res.append("[");
TreeSet<Integer> set = entry.getValue();
for(Integer integer : set) {
res.append(integer+", ");
}
res.deleteCharAt(res.length()-1);
res.deleteCharAt(res.length()-1);
res.append("], ");
}
res.deleteCharAt(res.length()-1);
res.deleteCharAt(res.length()-1);
res.append("]");
System.out.print(res.toString());
}
public double dis(double[][] point,int i,int j){
return (point[i][0] - point[j][0])*(point[i][0] - point[j][0])
+ (point[i][1] - point[j][1])*(point[i][1] - point[j][1]);
}
public int find(int[] data2,int i){
if(data2[i] == i)
return i;
return find(data2,data2[i]);
}
public void union(int[] data2,int i,int j){
i = find(data2,i);
j = find(data2,j);
if(i == j)
return;
if(i < j)
data2[j] = i;
else
data2[i] = j;
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
