问题陈述
人们在社交网络中相互联系。人 I 和人 J 之间的连接用 M I J 表示。当属于不同社区的两个人连接时，净效应是 I 和 J 所属的两个社区的合并。
一开始，有N个人代表N个社区。假设人 1 和 2 连接，后来 2 和 3 连接，那么 1,2 和 3 将属于同一个社区。
有两种类型的查询:
M I J => 包含人 I 和 J 的社区合并(如果他们属于不同的社区)。
Q I => 打印我所属的社区的大小。
我的方法:
我创建了一组空集。当两个人合并时，我会检查所有内部集合，如果找到其中任何一个，我会将它们添加到该集合中并进行拆分。
如果不是，我正在与这些人一起创建一个新的内部集合。
现在在这个父集合中，我需要将所有内部集合相互比较，如果找到交集，我应该合并两个内部集合，这是我无法做到的。
我的方法正确吗？但这是一个非常迭代的过程，有没有更好的方法来解决呢？
我的代码:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
int nPeople = sc.nextInt();
int queries = sc.nextInt();
Set<Set<Integer>> community = new HashSet<Set<Integer>>();
for(int i = 0 ; i<queries ; i++){
char query = sc.next().charAt(0);
if(query == 'Q'){
int p = sc.nextInt();
Set<Integer> tmpset = new HashSet<Integer>();
for( Set<Integer> innerSet : community){
for(Integer person : innerSet) {
if( person == p ){
for(Integer each : innerSet){
tmpset.add(each);
}
}
}
}
if(tmpset.size()!= 0) {
System.out.println(tmpset.size());
}
else {
System.out.println("1");
}
}
else if(query=='M'){
int person1 = sc.nextInt();
int person2 = sc.nextInt();
int c = 0;
loop:
for( Set<Integer> innerSet : community){
for(Integer person : innerSet) {
if( person == person1 || person == person2){
innerSet.add(person1);
innerSet.add(person2);
c++;
break loop;
}
}
}
if(c==0){
Set<Integer> tmpset = new HashSet<Integer>();
tmpset.add(person1);
tmpset.add(person2);
community.add(tmpset);
}
}
}
}
}
我的代码输出:包含集合的集合。
问题链接:https://www.hackerrank.com/challenges/merging-communities
在@Adamski 的帮助下解决了它，使用不相交的集合数据结构，但仍然不是那么有效的解决方案。
代码:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
int nPeople = sc.nextInt();
DisJoint comm = new DisJoint(nPeople);
int queries = sc.nextInt();
for(int k = 0 ; k<queries ; k++){
char query = sc.next().charAt(0);
if(query == 'Q'){
int person = sc.nextInt();
int personParent = comm.Find(person);
int community = 0;
for(int j =1 ; j<nPeople+1 ; j++){
int tmpParent = comm.Find(j);
if(personParent == tmpParent){
community++;
}
}
System.out.println(community);
}
if(query == 'M'){
int person1 = sc.nextInt();
int person2 = sc.nextInt();
comm.Union(person1,person2);
}
}
}
}
class DisJoint{
public int Count;
public int[] Parent;
public int[] Rank;
public DisJoint(int count){
this.Count = count;
this.Parent = new int[this.Count+1];
this.Rank = new int[this.Count+1];
for (int i = 1; i < this.Count+1; i++) {
this.Parent[i] = i;
this.Rank[i] = 0;
}
}
public int Find(int i){
if(i == Parent[i]){
return Parent[i];
}
else{
int result = Find(Parent[i]);
Parent[i] = result;
return result;
}
}
public void Union(int a, int b){
if(a>b){
int tmp = a;
a = b;
b = tmp;
}
int aroot = this.Find(a);
int broot = this.Find(b);
int arank = Rank[aroot];
int brank = Rank[broot];
if (aroot == broot){
return;
}
if (arank < brank) {
this.Parent[aroot] = broot;
}
else if (arank > brank) {
this.Parent[broot] = aroot;
}
else{
this.Parent[aroot] = broot;
Rank[broot]++;
}
}
}
请测试上述链接中的代码。
最佳答案
您是否考虑过使用数据结构来表示不相交的集合？例如这里:http://www.mathblog.dk/disjoint-set-data-structure/
基本前提是您定义一个类(例如 Person )并将您的社区集表示为单个数组。每个 Person 都包含一个返回数组的索引，指向自身或另一个 Person :
| Adam | Dave | Fred | Tom | James |
| 0 | 0 | 1 | 3 | 3 |
在上面的例子中，为了测试 Fred 和 Dave 是否在同一个社区中，你从每个 Person 开始并按照图到根人；即索引引用自身的人:
Fred -> Dave -> Adam
Dave -> Adam
(显然这里有一个优化，在第一次遍历期间，您在到达根之前实际上遇到了 Dave。)
相比之下，测试 James 和 Fred 是否在同一个社区:
James -> Tom
Fred -> Dave -> Adam
人们有不同的根源，因此属于不同的社区。
合并社区就是将一个社区的根人员重新指向另一个社区的根的情况。
推断社区的规模更为复杂；我将把它作为一个练习让你弄清楚!
关于java - 合并社区并由其成员寻找社区，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31452639/