Problemas de Programação

In order to solve this problem, I implemented the Weighted Quick-Union. First, I calculate the distance between every node (star) to the others. Then, if the distance between two stars is not more than the given distance, I connect the stars. Finally, in order to know the number of constellations, I need to know how many components I have. Although I have studied about Union-Find in the class "Algorithms, Part I", from Coursera (you can find more details here and here ), I used my own implementation to solve this problem. import java.io.*; import java.util.*; class Main  {      public static Coord[] coordinates;     public static int[] nodeParent;     public static int[] depth;         public static int count() {         int[] v = new int[nodeParent.length];                 for (int i = 1; i...

In order to solve this problem, I implemented the Weighted Quick-Union. I used a HashMap structure to map each creature to a number from 1 to numCreatures. Therefore, when I call the union method for two creatures, I only need to get the two numbers related to the creatures. Although I have studied about Union-Find in the class "Algorithms, Part I", from Coursera (you can find more details here and here ), I used my own implementation to solve this problem. import java.io.*; import java.util.*; class Main  {     public static int[] nodeParent;     public static int[] depth;     public static HashMap<String, Integer> creatures;        public static int count() {         int[] v = new int[nodeParent.length];                for (int i = 1; i < nodeParent.length; i++) {      ...

You can check another solution for this problem here . This solution is different from the previous one because when I connect two people, I change the root in order to link each node directly to its root. import java.io.*; import java.util.*; class Main  {      public static int[] parentNode;     public static int[] depth;         public static int countOccurrences() {         int[] v = new int[parentNode.length];                 for (int i = 1; i < parentNode.length; i++) {             v[root(parentNode[i])] += 1 ;         }                 int occurrences = -1;         for (int i = 1; i < v.length; i++) {  ...

Similarly to what I did in the problem "Ubiquitous Religions", I used the Union-Find approach to solve this problem. For this problem, instead of using another class to keep one node's parent and its depth, I am using two arrays (one array to keep the node's parent, and the other one to keep the depth). It simplifies some operations along the code.  Although I have studied about Union-Find in the class "Algorithms, Part I", from Coursera (you can find more details here and here ), I used my own implementation to solve this problem. import java.io.*; import java.util.*; class Main  {      public static int[] parentNode;     public static int[] depth;         public static int countOccurrences() {         int[] v = new int[parentNode.length];                 for (int i = 1; i < parentNode.length; i++)...

Another solution for the problem "All Roads Lead Where?". Check the previous solution here . Now, I do not use the class Element to create my queue in the Breadth-First Search method. Instead of creating a new class to handle with the list of cities, I use a HashMap<String, String> which maps a city to its parent. When I find the goal, I iterate through the HashMap to find the path from the current node to the start node . import java.io.*; import java.util.*; class Main  {     public static HashMap<String, ArrayList<String>> adjList = new HashMap<String, ArrayList<String>>();         public static void printAnswer(ArrayList<String> cities) {         for (int k = cities.size()-1; k >= 0; k--) {             System.out.print(cities.get(k).charAt(0));         }   ...

You can check other solutions for this problem here and here . This solution is different from the previous one ( here ) because when I connect two people, I change the root in order to link each node directly to its root. import java.io.*; import java.util.*; class Main  {     public static Element[] vector;        public static int count() {         int[] v = new int[vector.length];         for (int i = 1; i < vector.length; i++) {             v[root(vector[i].parent)] += 1;         }                 int components = 0;         for (int i = 1; i < v.length; i++) {             if (v[i] > 0) {    ...

You can check another solution for this problem here .  For this solution, I changed the structure used in the count() method. In the previous solution, I used an ArrayList of Integer. Now, I use a simple array. This solution is better because we know that the array will have at most "numPeople"+1 and an ArrayList resizes itself periodically. import java.io.*; import java.util.*; class Main  {     public static Element[] vector;        public static int count() {         int[] v = new int[vector.length];         for (int i = 1; i < vector.length; i++) {             v[root(vector[i].parent)] += 1;         }                 int components = 0;         for (int i = 1; i ...