Неверный ответ при вычислении минимального связующего дерева с использованием алгоритма Крускала

Question

Я пытаюсь решить this MST question on spoj с использованием алгоритма kruskal. моя программа, похоже, работает во всех тестовых случаях, но 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

Неправильная реализация вашей команды union-find. Рассмотрим пример

x -> y (y is parent of x) 

A -> B -> C 
D -> E 

Когда вы звоните checkCycle(A, D), что должно произойти, все 5 узлов должны идти в одном наборе, например:

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

Но что происходит в вашем коде:

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 и реализовать вариант сжатия путь, который улучшает сложность.