Wrong answer while calculating Minimum Spanning Tree Using Kruskal Algorithm

Question

I am Trying to solve this MST question on spoj using kruskal algorithm. my program seems to work on all test cases but spoj repeatedly is giving WA on this code.

I am not able to find any failing test cases on this code. Can someone please point out to what I am doing wrong.

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; } } }

Please put the code that you are actually submitting. I get compile error when I submit this code. — Saeid
– Saeid, Commented Oct 1, 2016 at 18:17

Saeid · Accepted Answer · 2016-10-01 19:38:15Z

Your implementation of union-find is not correct. Consider this example

x -> y ( y is parent of x ) A -> B -> C D -> E

When you call checkCycle( A, D) what should happen is all of the 5 nodes should go to one set, For example:

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

But what happens in your code is:

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

Which is obviously not correct.

You can change the checkCycle as below:

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; }

I strongly advise you to read the wikipedia article about Disjoint-set and implement the path compression version, which improves the complexity.

Collectives™ on Stack Overflow

Wrong answer while calculating Minimum Spanning Tree Using Kruskal Algorithm

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related