java - 合并社区并通过其成员找到社区

Question

问题陈述

人们在社交网络中相互联系。人 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]++;
        }
    }

}

请测试上述链接中的代码。

Answer 1

您是否考虑过使用数据结构来表示不相交的集合？例如这里:http://www.mathblog.dk/disjoint-set-data-structure/

基本前提是您定义一个类(例如 Person)并将您的社区集表示为单个数组。每个Person包含返回数组的索引，指向自身或另一个 Person :

| Adam | Dave | Fred | Tom | James |
| 0    | 0    | 1    | 3   | 3     |

在上面的示例中，要测试 Fred 和 Dave 是否在同一个社区中，您从每个人开始，然后按照图表找到根人；即索引引用自身的人:

Fred -> Dave -> Adam
Dave -> Adam

(显然这里有一个优化，在第一次遍历期间，您实际上在到达根目录之前遇到了 Dave。)

对比一下，测试James和Fred是否在同一个社区:

James -> Tom
Fred -> Dave -> Adam

人有不同的根源，因此属于不同的社区。

合并社区就是将一个社区的根人重新指向另一个社区的根。

推断社区的规模更为复杂；我将把它作为练习留给你去弄清楚!