Kruskal 알고리즘을 사용하여 최소 스패닝 트리를 계산하는 동안 잘못된 대답

Question

kruskal 알고리즘을 사용하여 this MST question on spoj을 (를) 해결하려고합니다. 내 프로그램은 모든 테스트 케이스에서 작동하는 것처럼 보이지만 spoj가이 코드에서 WA를 반복적으로 제공하고 있습니다.

이 코드에서 실패한 테스트 사례를 찾을 수 없습니다. 누군가 내가 잘못하고있는 것을 지적 할 수 있습니까?

import java.io.PrintWriter; 
import java.util.Arrays; 


public class CSTREET { 

    static final int MAX = 1002; 
    static Node edgeList[]; 
    static int parent[] = new int[MAX]; 


    public static void main(String[] args) throws Exception { 
     Reader in = new Reader(); 
     PrintWriter out = new PrintWriter(System.out, true); 
     int t = in.nextInt(); 
     while (t-- != 0) { 

      int price = in.nextInt(); 
      int vertices = in.nextInt(); 
      int edge = in.nextInt(); 
      int idx = 0; 
      edgeList = new Node[edge]; 
      for (int i = 1; i <= vertices; i++) { 
       parent[i] = i; 
      } 

      while (idx < edge) { 

       int src = in.nextInt(); 
       int dest = in.nextInt(); 
       int cost = in.nextInt(); 
       Node node = new Node(src, dest, cost); 

       edgeList[idx] = node; 
       idx++; 
      } 

      Arrays.sort(edgeList); 
      int edgeCount = 0; 


      long totalCost = 0; 
      idx = 0; 

      while (edgeCount < vertices-1) { 
       Node curEdge = edgeList[idx]; 
       if (!checkCycle(curEdge.src, curEdge.dest)) { 

        edgeCount++; 
        totalCost += curEdge.cost; 

       } 
       idx++; 

      } 
      out.println(totalCost * price); 
     } 
    } 


    static boolean checkCycle(int src, int dest) { 

     if (findParent(src) == findParent(dest)) { 
      return true; 
     } 

     while (parent[dest] != parent[src]) { 
      parent[dest] = src; 
      src = parent[src]; 
     } 

     return false; 

    } 

    static int findParent(int i) { 

     while (parent[i] != i) { 
      i = parent[i]; 
     } 

     return i; 
    } 


    static class Node implements Comparable<Node> { 

     int src; 
     int dest; 
     int cost; 

     public Node(int src, int dest, int cost) { 
      this.src = src; 
      this.dest = dest; 
      this.cost = cost; 
     } 

     @Override 
     public int compareTo(Node o) { 
      return this.cost - o.cost; 
     } 
    } 
} 

Answer 1

귀하의 유니온 찾기 구현이 올바르지 않습니다.

A -> B -> C 
D -> E -> C 

그러나 코드에서 일어나는 것은 :

당신이 checkCycle(A, D)를 호출 할 때 무엇을 어떻게해야하는 5 개 개의 모든 노드는 예를 들어, 한 세트에 가야입니다 예

x -> y (y is parent of x) 

A -> B -> C 
D -> E 

을 고려

A -> B -> C 
D -> C 
E 

분명히 맞지 않습니다.

당신은 checkCycle 다음과 같이 변경할 수 있습니다

static boolean checkCycle(int src, int dest) { 

    int srcRoot = findParent(src); 
    int destRoot = findParent(dest); 
    if (srcRoot == destRoot) { 
     return true; 
    } 
    parent[destRoot] = srcRoot; 
    return false; 
} 

난 강력하게 당신이 위키 피 디아 기사에 대한 Disjoint-set를 읽고 복잡성을 향상 경로 압축 버전을 구현하는 것이 좋습니다.