We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
It was a real fight with the timeouts. This exercise teaches why the algorithm performance counts.
java8
importjava.util.HashMap;importjava.util.Map;importjava.util.Scanner;importjava.util.stream.IntStream;publicclassSolution{staticclassNet{privateNetincluder;privateintsize;privateNet(intsize){this.size=size;}intgetSize(){returnsize;}NetgetIncluder(){returnincluder;}voidsetIncluder(Netincluder){this.includer=includer;}voidsetEffectiveIncluder(Netincluder){if(getIncluder()!=null&&getIncluder()!=includer){getIncluder().setEffectiveIncluder(includer);}setIncluder(includer);}NetgetEffectiveNet(){Netresult=this;while(result.getIncluder()!=null){result=result.getIncluder();}returnresult;}}publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);String[]nq=scanner.nextLine().split(" ");intn=Integer.parseInt(nq[0].trim());intq=Integer.parseInt(nq[1].trim());Map<Integer,Net>community=newHashMap<>();IntStream.rangeClosed(1,n).forEach(i->community.put(i,newNet(1)));IntStream.range(0,q).mapToObj(queriesRowItr->scanner.next()).forEachOrdered(op->{if("Q".equals(op)){intperson=scanner.nextInt();System.out.println(community.get(person).getEffectiveNet().getSize());}else{intperson1=scanner.nextInt();intperson2=scanner.nextInt();if(person1!=person2){Netnet1=community.get(person1);Netnet2=community.get(person2);NeteffectiveNet1=net1.getEffectiveNet();NeteffectiveNet2=net2.getEffectiveNet();if(effectiveNet1!=effectiveNet2){NetcommonNet=newNet(effectiveNet1.getSize()+effectiveNet2.getSize());effectiveNet1.setIncluder(commonNet);effectiveNet2.setIncluder(commonNet);// These calls help on the last 3 test timeoutsnet1.setEffectiveIncluder(commonNet);net2.setEffectiveIncluder(commonNet);}}}});}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merging Communities
You are viewing a single comment's thread. Return to all comments →
It was a real fight with the timeouts. This exercise teaches why the algorithm performance counts.
java8