Problem Statement
People connect with each other on a social network. The relationship between Person I and Person J is represented as M I J. When two people from different communities join together, the net effect is the merger of both communities to which I and J.
At the beginning there are N people representing N communities. Suppose that people 1 and 2 are connected, and later 2 and 3 are connected, then 1,2 and 3 will belong to one community.
There are two types of queries:
M i J => communities in which person I and J merge (if they belong to different communities).
Q i => print the size of the community to which I belong.
My approach:
I created an empty set of sets. When two people merge, I check all the inner sets, if I find them, I add them to this set and pull out. If not, I create a new inner set with these people. Now in this parent set I need to compare all the internal sets with each other, if an intersection is found, I have to combine both internal sets, which I can not do.
Is my approach right? But this is a very iterative process, is there a better way to solve it?
My code is:
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) {
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);
}
}
}
}
}
My output code is: a set containing sets.
Problem link: https://www.hackerrank.com/challenges/merging-communities
Solved it with @Adamski, using a disjoint set data structure, but still not a very efficient solution.
The code:
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) {
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]++;
}
}
}
Please check the code in the link provided.