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.
I use an int array (int[] parents) to keep tracking each element's root element, if any elements have the same root element, then they belong to the same set. Then you can just find the frequency of each value within that int[] parents.
Any suggestion is welcome for sure !
public static void main(String[] args) {
int[] parents = new int[30001];
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a, b;
while(n-->0){
a = sc.nextInt();
b = sc.nextInt();
System.out.println(a + " " + b);
if(parents[a] == 0) parents[a] = a;
if(parents[b] == 0) parents[b] = a;
//Disjoin set idea, keep updating the representative element of each set.
if(parents[a] != 0 || parents[b] != 0){
int low = Math.min(parents[a], parents[b]);
int high = Math.max(parents[a], parents[b]);
for(int i=0; i<parents.length; i++){
if(parents[i] == high)
parents[i] = low;
}
}
}
//convert int[] to Integer[] in order to use Collections.frequency(Integer[], int)
Integer[] newArray = new Integer[parents.length];
int i = 0;
for (int value : parents) {
newArray[i++] = value;
}
List<Integer> ints = Arrays.asList(newArray);
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int item : newArray) {
if(item != 0) {
int frequency = Collections.frequency(ints, item);
min = Math.min(min, frequency);
max = Math.max(max, frequency);
}
}
System.out.println(min + " " + max);
}
Components in a graph
You are viewing a single comment's thread. Return to all comments →
I use an int array (int[] parents) to keep tracking each element's root element, if any elements have the same root element, then they belong to the same set. Then you can just find the frequency of each value within that int[] parents.
Any suggestion is welcome for sure !
public static void main(String[] args) {