ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1160. Network

WA#5
Posted by Grim_Disciple 2 Oct 2009 18:23
need help. i used Kruskal's algorithm
Re: WA#5
Posted by esbybb 3 Feb 2016 06:59
hi,
you already solved this problem perhaps someone else might stuck in this test also:

for Kruskal's algorithm i used to use this union method and got WA5,

    static void union(int su, int sv) {
        int segu = seg_in_hub[su];
        seg_in_hub[sv] = segu;
    }//seg_in_hub[1..H+1] initialized with 1,2,3..H
Instead, i rewrote this method and the solution got accepted
    static int union(int su, int sv) {
        int c = 1;
        int segu = seg_in_hub[su];
        int segv = seg_in_hub[sv];
        for (int i=0; i<seg_in_hub.length; i++) {
            if (seg_in_hub[i] == segu) {
                c++;
                seg_in_hub[i] = segv;
            }
        }
        return c;
    }

//Also check if method returns H then break the loop