An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes, and the graph may not be connected.
Implement the DistanceLimitedPathsExist class:
DistanceLimitedPathsExist(int n, int[][] edgeList) Initializes the class with an undirected graph.
boolean query(int p, int q, int limit) Returns true if there exists a path from p to q such that each edge on the path has a distance strictly less thanlimit, and otherwise false.
Example 1:
Input
["DistanceLimitedPathsExist", "query", "query", "query", "query"]
[[6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]], [2, 3, 2], [1, 3, 3], [2, 0, 3], [0, 5, 6]]
Output
[null, true, false, true, false]
Explanation
DistanceLimitedPathsExist distanceLimitedPathsExist = new DistanceLimitedPathsExist(6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]);
distanceLimitedPathsExist.query(2, 3, 2); // return true. There is an edge from 2 to 3 of distance 1, which is less than 2.
distanceLimitedPathsExist.query(1, 3, 3); // return false. There is no way to go from 1 to 3 with distances strictly less than 3.
distanceLimitedPathsExist.query(2, 0, 3); // return true. There is a way to go from 2 to 0 with distance < 3: travel from 2 to 3 to 0.
distanceLimitedPathsExist.query(0, 5, 6); // return false. There are no paths from 0 to 5.
classPersistentUnionFind{privatefinalintinf=1<<30;privateint[]rank;privateint[]parent;privateint[]version;publicPersistentUnionFind(intn){rank=newint[n];parent=newint[n];version=newint[n];for(inti=0;i<n;i++){parent[i]=i;version[i]=inf;}}publicintfind(intx,intt){if(parent[x]==x||version[x]>=t){returnx;}returnfind(parent[x],t);}publicbooleanunion(inta,intb,intt){intpa=find(a,inf);intpb=find(b,inf);if(pa==pb){returnfalse;}if(rank[pa]>rank[pb]){version[pb]=t;parent[pb]=pa;}else{version[pa]=t;parent[pa]=pb;if(rank[pa]==rank[pb]){rank[pb]++;}}returntrue;}}publicclassDistanceLimitedPathsExist{privatePersistentUnionFindpuf;publicDistanceLimitedPathsExist(intn,int[][]edgeList){puf=newPersistentUnionFind(n);Arrays.sort(edgeList,(a,b)->a[2]-b[2]);for(vare:edgeList){puf.union(e[0],e[1],e[2]);}}publicbooleanquery(intp,intq,intlimit){returnpuf.find(p,limit)==puf.find(q,limit);}}/** * Your DistanceLimitedPathsExist object will be instantiated and called as such: * DistanceLimitedPathsExist obj = new DistanceLimitedPathsExist(n, edgeList); * boolean param_1 = obj.query(p,q,limit); */
classPersistentUnionFind{private:vector<int>rank;vector<int>parent;vector<int>version;public:PersistentUnionFind(intn):rank(n,0),parent(n),version(n,INT_MAX){for(inti=0;i<n;i++){parent[i]=i;}}intfind(intx,intt){if(parent[x]==x||version[x]>=t){returnx;}returnfind(parent[x],t);}boolunionSet(inta,intb,intt){intpa=find(a,INT_MAX);intpb=find(b,INT_MAX);if(pa==pb){returnfalse;}if(rank[pa]>rank[pb]){version[pb]=t;parent[pb]=pa;}else{version[pa]=t;parent[pa]=pb;if(rank[pa]==rank[pb]){rank[pb]++;}}returntrue;}};classDistanceLimitedPathsExist{private:PersistentUnionFindpuf;public:DistanceLimitedPathsExist(intn,vector<vector<int>>&edgeList):puf(n){sort(edgeList.begin(),edgeList.end(),[](constvector<int>&a,constvector<int>&b){returna[2]<b[2];});for(constauto&edge:edgeList){puf.unionSet(edge[0],edge[1],edge[2]);}}boolquery(intp,intq,intlimit){returnpuf.find(p,limit)==puf.find(q,limit);}};/** * Your DistanceLimitedPathsExist object will be instantiated and called as such: * DistanceLimitedPathsExist* obj = new DistanceLimitedPathsExist(n, edgeList); * bool param_1 = obj->query(p,q,limit); */
typePersistentUnionFindstruct{rank[]intparent[]intversion[]int}funcNewPersistentUnionFind(nint)*PersistentUnionFind{rank:=make([]int,n)parent:=make([]int,n)version:=make([]int,n)fori:=0;i<n;i++{parent[i]=i}return&PersistentUnionFind{rank:rank,parent:parent,version:version,}}func(uf*PersistentUnionFind)find(xint,tint)int{ifuf.parent[x]==x||uf.version[x]>=t{returnx}returnuf.find(uf.parent[x],t)}func(uf*PersistentUnionFind)union(a,b,tint)bool{pa:=uf.find(a,int(^uint(0)>>1))pb:=uf.find(b,int(^uint(0)>>1))ifpa==pb{returnfalse}ifuf.rank[pa]>uf.rank[pb]{uf.version[pb]=tuf.parent[pb]=pa}else{uf.version[pa]=tuf.parent[pa]=pbifuf.rank[pa]==uf.rank[pb]{uf.rank[pb]++}}returntrue}typeDistanceLimitedPathsExiststruct{puf*PersistentUnionFind}funcConstructor(nint,edgeList[][]int)DistanceLimitedPathsExist{sort.Slice(edgeList,func(i,jint)bool{returnedgeList[i][2]<edgeList[j][2]})puf:=NewPersistentUnionFind(n)for_,edge:=rangeedgeList{puf.union(edge[0],edge[1],edge[2])}returnDistanceLimitedPathsExist{puf:puf,}}func(dle*DistanceLimitedPathsExist)Query(p,q,limitint)bool{returndle.puf.find(p,limit)==dle.puf.find(q,limit)}/** * Your DistanceLimitedPathsExist object will be instantiated and called as such: * obj := Constructor(n, edgeList); * param_1 := obj.Query(p,q,limit); */
classPersistentUnionFind{privaterank:number[];privateparent:number[];privateversion:number[];constructor(n:number){this.rank=Array(n).fill(0);this.parent=Array.from({length:n},(_,i)=>i);this.version=Array(n).fill(Infinity);}find(x:number,t:number):number{if(this.parent[x]===x||this.version[x]>=t){returnx;}returnthis.find(this.parent[x],t);}union(a:number,b:number,t:number):boolean{constpa=this.find(a,Infinity);constpb=this.find(b,Infinity);if(pa===pb){returnfalse;}if(this.rank[pa]>this.rank[pb]){this.version[pb]=t;this.parent[pb]=pa;}else{this.version[pa]=t;this.parent[pa]=pb;if(this.rank[pa]===this.rank[pb]){this.rank[pb]++;}}returntrue;}}classDistanceLimitedPathsExist{privatepuf:PersistentUnionFind;constructor(n:number,edgeList:number[][]){this.puf=newPersistentUnionFind(n);edgeList.sort((a,b)=>a[2]-b[2]);for(const[u,v,dis]ofedgeList){this.puf.union(u,v,dis);}}query(p:number,q:number,limit:number):boolean{returnthis.puf.find(p,limit)===this.puf.find(q,limit);}}/** * Your DistanceLimitedPathsExist object will be instantiated and called as such: * var obj = new DistanceLimitedPathsExist(n, edgeList) * var param_1 = obj.query(p,q,limit) */