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.
packagemainimport("bufio""fmt""io""os""strconv""strings""sort")typeUnionFindstruct{parent[]int32rank[]int32numSetsint32setSize[]int32}funcNewUf(Vint32)*UnionFind{rank:=make([]int32,V+1)parent:=make([]int32,V+1)setSize:=make([]int32,V+1)fori:=int32(1);i<=V;i++{parent[i]=isetSize[i]=1}return&UnionFind{parent,rank,V,setSize,}}func(ufUnionFind)IsSameSet(iint32,jint32)bool{ifuf.FindSet(i)==uf.FindSet(j){returntrue}returnfalse}func(uf*UnionFind)FindSet(iint32)int32{if(*uf).parent[i]==i{returni}(*uf).parent[i]=uf.FindSet((*uf).parent[i])return(*uf).parent[i]}func(uf*UnionFind)UnionSet(iint32,jint32){if!(*uf).IsSameSet(i,j){x:=(*uf).FindSet(i)y:=(*uf).FindSet(j)if(*uf).rank[x]>(*uf).rank[y]{(*uf).parent[y]=x(*uf).setSize[x]+=(*uf).setSize[y]}else{(*uf).parent[x]=y(*uf).setSize[y]+=(*uf).setSize[x]if(*uf).rank[x]==(*uf).rank[y]{(*uf).rank[y]++}}(*uf).numSets--}}/* * Complete the 'kruskals' function below. * * The function is expected to return an INTEGER. * The function accepts WEIGHTED_INTEGER_GRAPH g as parameter. *//* * For the weighted graph, <name>: * * 1. The number of nodes is <name>Nodes. * 2. The number of edges is <name>Edges. * 3. An edge exists between <name>From[i] and <name>To[i]. The weight of the edge is <name>Weight[i]. * */funckruskals(gNodesint32,gFrom[]int32,gTo[]int32,gWeight[]int32)int32{varedgeList[][]int32fori:=0;i<len(gFrom);i++{edge:=[]int32{gFrom[i],gTo[i],gWeight[i]}edgeList=append(edgeList,edge)}sort.Slice(edgeList,func(i,jint)bool{returnedgeList[i][2]<edgeList[j][2]})mstWeight:=int32(0)uf:=NewUf(gNodes)fori:=0;i<len(edgeList)&&(*uf).numSets>1;i++{edge:=edgeList[i]if!(*uf).IsSameSet(edge[0],edge[1]){mstWeight+=edge[2](*uf).UnionSet(edge[0],edge[1])}}returnmstWeight}funcmain(){reader:=bufio.NewReaderSize(os.Stdin,16*1024*1024)stdout,err:=os.Create(os.Getenv("OUTPUT_PATH"))checkError(err)deferstdout.Close()writer:=bufio.NewWriterSize(stdout,16*1024*1024)gNodesEdges:=strings.Split(readLine(reader)," ")gNodes,err:=strconv.ParseInt(gNodesEdges[0],10,64)checkError(err)gEdges,err:=strconv.ParseInt(gNodesEdges[1],10,64)checkError(err)vargFrom,gTo,gWeight[]int32fori:=0;i<int(gEdges);i++{edgeFromToWeight:=strings.Split(readLine(reader)," ")edgeFrom,err:=strconv.ParseInt(edgeFromToWeight[0],10,64)checkError(err)edgeTo,err:=strconv.ParseInt(edgeFromToWeight[1],10,64)checkError(err)edgeWeight,err:=strconv.ParseInt(edgeFromToWeight[2],10,64)checkError(err)gFrom=append(gFrom,int32(edgeFrom))gTo=append(gTo,int32(edgeTo))gWeight=append(gWeight,int32(edgeWeight))}res:=kruskals(int32(gNodes),gFrom,gTo,gWeight)fmt.Fprintf(writer,"%d\n",res)writer.Flush()}funcreadLine(reader*bufio.Reader)string{str,_,err:=reader.ReadLine()iferr==io.EOF{return""}returnstrings.TrimRight(string(str),"\r\n")}funccheckError(errerror){iferr!=nil{panic(err)}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Kruskal (MST): Really Special Subtree
You are viewing a single comment's thread. Return to all comments →
Golang solution