[Kruskal MST] import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; class Result { /* * Complete the 'getCost' function below. * * The function accepts WEIGHTED_INTEGER_GRAPH g as parameter. */ /* * For the weighted graph, <name>: * * 1. The number of nodes is <name>Nodes. * 2. The number of edges is <name>Edges. * 3. An edge exists between <name>From[i] and <name>To[i]. The weight of the edge is <name>Weight[i]. * */ public static class Node implements Comparable<Node>{ int from; int to; int weight; Node(int from, int to, int weight){ this.from = from; this.to = to; this.weight = weight; } @Override public int compareTo(Node arg0) { // TODO Auto-generated method stub return this.weight <= arg0.weight ? -1 : 1; } } public static int find(int[] parents, int a) { if(a == parents[a]) return a; parents[a] = find(parents, parents[a]); return parents[a]; } public static void union(int[] parents, int a, int b) { if(a == b )return; int rootA = find(parents, a); int rootB = find(parents, b); parents[rootB] = rootA; } public static void getCost(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) { // Print your answer within the function and return nothing Iterator[] it = new Iterator[3]; it[0] = gFrom.iterator(); it[1] = gTo.iterator(); it[2] = gWeight.iterator(); PriorityQueue<Node> minWeightQue = new PriorityQueue<>(); while(it[0].hasNext()) { int from = (int)it[0].next(); int to= (int)it[1].next(); int weight= (int)it[2].next(); minWeightQue.add(new Node(from, to , weight)); } int[] parents = new int[gNodes + 1]; int[] minDistance = new int[gNodes + 1]; for(int i = 0; i < parents.length; i++) { parents[i] = i; } // int index = 0; int max = 0; while(minWeightQue.isEmpty() == false) { Node temp = minWeightQue.poll(); int to = temp.to; int from = temp.from; int rootTo = find(parents, to); int rootFrom = find(parents, from); if(rootTo == rootFrom) continue; union(parents, rootTo, rootFrom); // minDistance[index++] = temp.weight; if(temp.weight > max) max = temp.weight; if(find(parents, 1) == find(parents, gNodes)) break; } if(find(parents, 1) != find(parents, gNodes)) { System.out.println("NO PATH EXISTS"); return; } /* for(int i = 0; i < index ; i++) { if(minDistance[i] > max) max = minDistance[i]; } */ System.out.println(max); } } public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] gNodesEdges = bufferedReader.readLine().replaceAll("\\s+$", "").split(" "); int gNodes = Integer.parseInt(gNodesEdges[0]); int gEdges = Integer.parseInt(gNodesEdges[1]); List<Integer> gFrom = new ArrayList<>(); List<Integer> gTo = new ArrayList<>(); List<Integer> gWeight = new ArrayList<>(); IntStream.range(0, gEdges).forEach(i -> { try { String[] gFromToWeight = bufferedReader.readLine().replaceAll("\\s+$", "").split(" "); gFrom.add(Integer.parseInt(gFromToWeight[0])); gTo.add(Integer.parseInt(gFromToWeight[1])); gWeight.add(Integer.parseInt(gFromToWeight[2])); } catch (IOException ex) { throw new RuntimeException(ex); } }); Result.getCost(gNodes, gFrom, gTo, gWeight); bufferedReader.close(); } } [prims] import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; class Result { /* * Complete the 'getCost' function below. * * The function accepts WEIGHTED_INTEGER_GRAPH g as parameter. */ /* * For the weighted graph, <name>: * * 1. The number of nodes is <name>Nodes. * 2. The number of edges is <name>Edges. * 3. An edge exists between <name>From[i] and <name>To[i]. The weight of the edge is <name>Weight[i]. * */ public static class Node implements Comparable<Node>{ int to; int weight; Node(int to, int weight){ this.to = to; this.weight = weight; } @Override public int compareTo(Node arg0) { // TODO Auto-generated method stub return this.weight <= arg0.weight ? -1 : 1; } } public static void getCost(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) { // Print your answer within the function and return nothing ArrayList<Node> nodes[] = new ArrayList[gNodes+1]; for(int i = 0; i < nodes.length; i++) { nodes[i] = new ArrayList<>(); } Iterator[] it = new Iterator[3]; it[0] = gFrom.iterator(); it[1] = gTo.iterator(); it[2] = gWeight.iterator(); while(it[0].hasNext()) { int from = (int)it[0].next(); int to= (int)it[1].next(); int weight= (int)it[2].next(); nodes[to].add(new Node(from, weight)); nodes[from].add(new Node(to, weight)); } Queue<Integer> haveToGo = new LinkedList<>(); PriorityQueue<Node> minWeightQue = new PriorityQueue<>(); haveToGo.add(1); int[] isMoved = new int[gNodes+1]; isMoved[1] = -1; int maxWeight = 0; while(haveToGo.isEmpty() == false) { int cur = haveToGo.poll(); for(int i = 0; i < nodes[cur].size(); i++) { Node next = nodes[cur].get(i); int to = next.to; int weight = next.weight; // 1. 안가본 곳이라면, if(isMoved[to] == 0) { minWeightQue.add(new Node(to, weight)); } } // 2. 최소치를 본다. while(minWeightQue.isEmpty() == false) { Node minNode = minWeightQue.poll(); int to = minNode.to; int weight = minNode.weight; // 안가본 곳이라면, if(isMoved[to] == 0) { int newWeight; // 간선 가중치를 갱신한다 : if(isMoved[cur] == 0) { // 최초 갱신 newWeight = weight; } else { // 지난것과 비교 후 최대치 newWeight = weight > isMoved[cur] ? weight : isMoved[cur]; } isMoved[to] = newWeight; if(maxWeight < newWeight) maxWeight = newWeight; //다음 갈 곳을 지정하고, if(to == gNodes) { break; } else { haveToGo.add(to); } break; } } } if(isMoved[gNodes] == 0) { System.out.println("NO PATH EXISTS"); } else { System.out.println(isMoved[gNodes]); } } } public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] gNodesEdges = bufferedReader.readLine().replaceAll("\\s+$", "").split(" "); int gNodes = Integer.parseInt(gNodesEdges[0]); int gEdges = Integer.parseInt(gNodesEdges[1]); List<Integer> gFrom = new ArrayList<>(); List<Integer> gTo = new ArrayList<>(); List<Integer> gWeight = new ArrayList<>(); IntStream.range(0, gEdges).forEach(i -> { try { String[] gFromToWeight = bufferedReader.readLine().replaceAll("\\s+$", "").split(" "); gFrom.add(Integer.parseInt(gFromToWeight[0])); gTo.add(Integer.parseInt(gFromToWeight[1])); gWeight.add(Integer.parseInt(gFromToWeight[2])); } catch (IOException ex) { throw new RuntimeException(ex); } }); Result.getCost(gNodes, gFrom, gTo, gWeight); bufferedReader.close(); } } |
