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.
This is a typical Union Find problem. As long as you know Union Find, this problem is straightforward. Below is a Java Union Find(with path compression) solution:
importjava.io.*;importjava.math.*;importjava.security.*;importjava.text.*;importjava.util.*;importjava.util.concurrent.*;importjava.util.regex.*;publicclassSolution{staticclassUnionFind{Map<Integer,Integer>parents;Map<Integer,Integer>sizes;intmax;publicUnionFind(){parents=newHashMap<>();sizes=newHashMap<>();max=0;}publicvoidunion(intv1,intv2){if(!parents.containsKey(v1)){parents.put(v1,v1);sizes.put(v1,1);}if(!parents.containsKey(v2)){parents.put(v2,v2);sizes.put(v2,1);}intp1=find(v1),p2=find(v2);if(p1==p2)return;ints1=sizes.get(p1),s2=sizes.get(p2);if(s1<s2){parents.put(p1,p2);sizes.put(p2,s1+s2);if(s1+s2>max)max=s1+s2;}else{parents.put(p2,p1);sizes.put(p1,s1+s2);if(s1+s2>max)max=s1+s2;}}publicintfind(intv){while(parents.get(v)!=v){parents.put(v,parents.get(parents.get(v)));v=parents.get(v);}returnv;}}// Complete the maxCircle function below.staticint[]maxCircle(int[][]queries){UnionFinduf=newUnionFind();int[]res=newint[queries.length];for(inti=0;i<queries.length;i++){uf.union(queries[i][0],queries[i][1]);res[i]=uf.max;}returnres;}privatestaticfinalScannerscanner=newScanner(System.in);publicstaticvoidmain(String[]args)throwsIOException{BufferedWriterbufferedWriter=newBufferedWriter(newFileWriter(System.getenv("OUTPUT_PATH")));intq=scanner.nextInt();scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");int[][]queries=newint[q][2];for(inti=0;i<q;i++){String[]queriesRowItems=scanner.nextLine().split(" ");scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");for(intj=0;j<2;j++){intqueriesItem=Integer.parseInt(queriesRowItems[j]);queries[i][j]=queriesItem;}}int[]ans=maxCircle(queries);for(inti=0;i<ans.length;i++){bufferedWriter.write(String.valueOf(ans[i]));if(i!=ans.length-1){bufferedWriter.write("\n");}}bufferedWriter.newLine();bufferedWriter.close();scanner.close();}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Friend Circle Queries
You are viewing a single comment's thread. Return to all comments →
This is a typical Union Find problem. As long as you know Union Find, this problem is straightforward. Below is a Java Union Find(with path compression) solution: