We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This is what i did, before any prior knowledge of disjoint set, union.. but it worked.. Hurray**
for my code complexity is very low as:- for all querys, finding length of community is being done in O(1) and merging for all queriest take total of O(N) or O(total nodes ).. (dont misunderstood it by each Query takes O(N).. its sum of all query takes overall O(n) in merging).. so total complexity is (Q.O(1)+N)
package DataStrucure;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Merging_Communities1 {
static class ArrayListWithId {
int id;
Stack<Integer> stack = new Stack();
public ArrayListWithId(int id) {
this.id = id;
}
}
static boolean NodeVisited[];
static ArrayList<Integer> edges[];
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int Q = s.nextInt();
ArrayListWithId connectedGroup[] = new ArrayListWithId[N + 1];
for (int i = 1; i < N + 1; i++) {
connectedGroup[i] = new ArrayListWithId(i);
connectedGroup[i].stack.push(i);
}
for (int i = 0; i < Q; i++) {
String Qtype = s.next();
if (Qtype.equals("M")) {
int n1 = s.nextInt();
int n2 = s.nextInt();
//int group1=connectedGroup[n1];
// int group2=connectedGroup[n2];
merge(n1, n2, connectedGroup);
} else {
int n1 = s.nextInt();
int ans = connectedGroup[n1].stack.size();
System.out.println(ans);
}
}
}
private static int count(int group, int[] connectedGroup) {
int counter = 0;
for (int i = 1; i < connectedGroup.length; i++) {
if (connectedGroup[i] == group) {
counter++;
}
}
return counter;
}
private static void merge(int n1, int n2, ArrayListWithId connectedGroup[]) {
ArrayListWithId alI1 = connectedGroup[n1];
ArrayListWithId alI2 = connectedGroup[n2];
if (alI1.id != alI2.id) {
if (alI1.stack.size() < alI2.stack.size()) {
ArrayListWithId temp;
temp = alI1;
alI1 = alI2;
alI2 = temp;
}
//I am assuming first stack is bigger than second
Stack<Integer> st2 = alI2.stack;
Stack<Integer> st1 = alI1.stack;
while (!st2.isEmpty()) {
int num = st2.pop();
st1.push(num);
connectedGroup[num] = alI1;
}
}
}
}
**
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merging Communities
You are viewing a single comment's thread. Return to all comments →
This is what i did, before any prior knowledge of disjoint set, union.. but it worked.. Hurray**
for my code complexity is very low as:- for all querys, finding length of community is being done in O(1) and merging for all queriest take total of O(N) or O(total nodes ).. (dont misunderstood it by each Query takes O(N).. its sum of all query takes overall O(n) in merging).. so total complexity is (Q.O(1)+N)