Problemas de Programação

I used Depth-First Search to solve this problem. import java.io.*; class Main {     public static int[][] matrix;     public static boolean[][] visited;     public static int[] vx = {-1,-1,-1,0,0,1,1,1};     public static int[] vy = {-1,0,1,-1,1,-1,0,1};     public static int row;     public static int col;     public static int count;         public static void dfs(int currX, int currY) {         if (currX < 0 || currY < 0 || currX >= row || currY >= col || matrix[currX][currY] == 0 || visited[currX][currY] == true) {             return;         }                 visited[currX][currY] = true;         count++;         for (int i = 0; i < 8; i++) {             int nextX = currX+vx[i];             int nextY = currY+vy[i];             dfs(nextX, nextY);         }     }         public static void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 String line = br.readLine(

If you want to see another solution for this problem, click here . I used Prim's algorithm to solve this problem. import java.io.*; import java.util.*; import java.lang.Math; class Main {     public static Coord[] cities;     public static int numStates;     public static double lengthRoads;     public static double lengthRailroads;         public static Comparator<Edge> lengthComparator = new Comparator<Edge>() {         public int compare(Edge e1, Edge e2) {             if (e1.length-e2.length < 0) {                 return -1;             }             else if (e1.length-e2.length > 0) {                 return 1;             }                         return 0;         }     };         public static void prim(int start, int numCities, int maxLength) {         Queue<Edge> queue = new PriorityQueue<Edge>(numCities, lengthComparator);         Edge e = new Edge(start, 0.0);         queue.add(e);                 HashSet<Integer> visited = new Ha

I used Kruskal's algorithm to solve this problem. import java.io.*; import java.util.*; import java.lang.Math; class Main {     public static Coord[] cities;     public static ArrayList<Distance> distances;     public static int[] nodeParent;     public static int[] depth;         public static int root(int n) {         int currN = n;         while (nodeParent[currN] != currN) {             currN = nodeParent[currN];         }                 return currN;     }         public static boolean union(int n1, int n2) {         int rootN1 = root(n1);         int rootN2 = root(n2);                 if (rootN1 != rootN2) {             if (depth[rootN1] <= depth[rootN2]) {                 nodeParent[rootN2] = nodeParent[rootN1];                 if (depth[rootN1] == depth[rootN2]) {                     depth[rootN1]++;                 }             }             else {                 nodeParent[rootN1] = nodeParent[rootN2];             }                         return true;     

I used Dijkstra's algorithm to solve this problem. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<Edge>> adjList;     public static String pathNodes;         public static Comparator<Path> costComparator = new Comparator<Path>() {         public int compare(Path p1, Path p2) {             return p1.e.cost-p2.e.cost;         }     };         public static int dijkstra(int start, int end) {         Queue<Path> queue = new PriorityQueue<Path>(10, costComparator);         Path p = new Path(new Edge(start, 0), "");         queue.add(p);         HashSet<Integer> visited = new HashSet<Integer>();                 while (queue.size() > 0) {             Path curr = queue.poll();             int currNode = curr.e.node;             int currCost = curr.e.cost;             StringBuilder currPath = new StringBuilder(curr.path);                         if (visited.contains(currNode)) {

If you want to see another solution for this problem, click here . I used Prim's algorithm to solve this problem. import java.io.*; import java.util.*; class Main {     public static HashMap<Integer, ArrayList<Edge>> adjList;         public static Comparator<Edge> costComparator = new Comparator<Edge>() {         public int compare(Edge e1, Edge e2) {             return e1.cost-e2.cost;         }     };         public static int prim(int start, int numJunctions) {         Queue<Edge> queue = new PriorityQueue<Edge>(numJunctions, costComparator);         Edge e = new Edge(start, 0);         queue.add(e);                 HashSet<Integer> visited = new HashSet<Integer>();                 int cost = 0;         while (queue.size() > 0) {             Edge curr = queue.poll();             int currJunction = curr.junction;             int currCost = curr.cost;                         if (visited.contains(currJunction)) {              

I used Kruskal's algorithm to solve this problem. import java.io.*; import java.util.*; class Main  {     public static int[] nodeParent;     public static int[] depth;         public static int root(int n) {         int currN = n;         while (nodeParent[currN] != currN) {             currN = nodeParent[currN];         }                 return currN;     }         public static boolean union(int n1, int n2) {         int rootN1 = root(n1);         int rootN2 = root(n2);                 if (rootN1 != rootN2) {             if (depth[rootN1] >= depth[rootN2]) {                 nodeParent[rootN2] = nodeParent[rootN1];                                if (depth[rootN1] == depth[rootN2]) {                     depth[rootN1]++;                 }             }             else {                 nodeParent[rootN1] = nodeParent[rootN2];             }                         return true;         }                 return false;     }         public static void process() throws NumberForm

I used Kosaraju's algorithm to solve this problem. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<Integer>> adjListOut;     public static HashMap<Integer, ArrayList<Integer>> adjListOutReverse;     public static boolean[] visited;     public static Deque<Integer> stack;         public static void dfsReverse(int intersection) {         if (visited[intersection]) {             return;         }                 visited[intersection] = true;         ArrayList<Integer> reachIntersec = adjListOutReverse.get(intersection);         for (int i = 0; i < reachIntersec.size(); i++) {             dfsReverse(reachIntersec.get(i));         }     }         public static void dfs(int intersection) {         if (visited[intersection]) {             return;         }                 visited[intersection] = true;         ArrayList<Integer> reachIntersec = adjListOut.get(intersection);         for (int i =

In order to solve this problem, I used Kosaraju's algorithm, which helps to find the strongly connected components. Each strongly connected component was associated with an identification. Then, I used these identifications to check if two dominos were in the same connected component. If not, the connected component of the domino to be reached would have its degree increased. The answer is the number of connected components whose degree is equal to zero. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<Integer>> adjListOut;     public static HashMap<Integer, ArrayList<Integer>> adjListOutReverse;     public static HashMap<Integer, Integer> identities;     public static Deque<Integer> stack;     public static boolean[] visited;         public static void dfsReverse(int vertex, int idt) {         if (visited[vertex]) {             return;         }                 identities.put(vertex, idt);  

If you want to see another solution for this problem, click here . I used Prim's algorithm to solve this problem. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<Edge>> adjList;     public static HashSet<Integer> visited;     public static int[][] costEdges;         public static Comparator<EdgeWithParent> costComparator = new Comparator<EdgeWithParent>() {         public int compare(EdgeWithParent e1, EdgeWithParent e2) {             return e1.e.cost-e2.e.cost;         }     };         public static void prim(int start, int numNodes) {         Queue<EdgeWithParent> queue = new PriorityQueue<EdgeWithParent>(numNodes, costComparator);         EdgeWithParent ewp = new EdgeWithParent(new Edge(start, 0), start);         queue.add(ewp);                 int numNodesVisited = 0;         while (queue.size() > 0) {             EdgeWithParent curr = queue.poll();             int currNode = curr

I used Kruskal's algorithm to solve this problem. import java.io.*; import java.util.*; class Main  {     public static ArrayList<Edge> listEdges;     public static ArrayList<Integer> costCycles;     public static int[] nodeParent;     public static int[] depth;         public static int root(int n) {         int currN = n;         while (nodeParent[currN] != currN) {             currN = nodeParent[currN];         }                 return currN;     }         public static boolean union(int n1, int n2) {         int rootN1 = root(n1);         int rootN2 = root(n2);                 if (rootN1 != rootN2) {             if (depth[rootN1] >= depth[rootN2]) {                 nodeParent[rootN2] = nodeParent[rootN1];                 if (depth[rootN1] == depth[rootN2]) {                     depth[rootN1]++;                 }             }             else {                 nodeParent[rootN1] = nodeParent[rootN2];             }                         return true;         }

I used Breadth-First Search to solve this problem. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<Integer>> adjList;             public static int bfs(int start, int end) {         Queue<Camarade> queue = new ArrayDeque<Camarade>();         Camarade c = new Camarade(start, 0);         queue.add(c);                 HashSet<Integer> addedToQueue = new HashSet<Integer>();         addedToQueue.add(start);                 while (queue.size() > 0) {             Camarade curr = queue.poll();             int currCamarade = curr.camarade;             int currDepth = curr.depth;                         if (currCamarade == end) {                 return currDepth-1; // the last one is the guy who will help             }                         ArrayList<Integer> reachCamarades = adjList.get(currCamarade);             for (int i = 0; i < reachCamarades.size(); i++) {                 int nextCamarade