Posts

Showing posts from April, 2016

(UVA) Counting Cells in a Blob - Solution

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++; ...

(UVA) Transportation System - Solution 2

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) {   ...

(UVA) Transportation System - Solution 1

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);       ...

(UVA) Non-Stop Travel - Solution

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);      ...

(UVA) Dark Roads - Solution 2

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);     ...

(UVA) Dark Roads - Solution 1

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) { ...

(UVA) Come and Go - Solution

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 <...

(UVA) Dominos - Solution

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) { ...

(UVA) Heavy Cycle Edges - Solution 2

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>(numNo...

(UVA) Heavy Cycle Edges - Solution 1

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);       ...

(UVA) The mysterious X network - Solution

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();   ...