a_lc_检查边长度限制的路径是否存在(并查集离线处理)

标签:list   集中   lambda   one   数组   lis   for   长度   pre   

给一个数组queries,queries[j]=[p, q, limit],你的任务是对于每个查询,判断是否存在从 p 到 q 的路径,且这条路径上的每一条边都 严格小于 limit。

2 <= n <= 105
1 <= edgeList.length, queries.length <= 105

思路:问的是两个结点带限制下的连通性;对于每个查询qs[i],可以把边集es中边长小于qs[i].limit的边全都加到并查集中,如果给定的边集一直满足就一直加,然再判端qs[i]的两个点的连通性即可

class UF:
    def __init__(self, n) -> None:
        self.fa=[i for i in range(n)]
    def find(self, u):
        if u==self.fa[u]: return u
        self.fa[u]=self.find(self.fa[u])
        return self.fa[u]
    def union(self, u, v):
        fu,fv=self.find(u),self.find(v)
        self.fa[fu]=fv
class Solution:
    def distanceLimitedPathsExist(self, n: int, es: List[List[int]], qs: List[List[int]]) -> List[bool]:
        m,lenQ=len(es),len(qs)
        qs=[[u,v,w,idx] for idx,[u,v,w] in enumerate(qs)]
        uf=UF(n)
        qs.sort(key=lambda q:q[2])
        es.sort(key=lambda e:e[2])

        j,ans=0,[0]*lenQ
        for i in range(lenQ):
            while j<m and es[j][2]<qs[i][2]:
                uf.union(es[j][0], es[j][1])
                j+=1
            ans[qs[i][3]]=uf.find(qs[i][0])==uf.find(qs[i][1])
        return ans

ps:刚刚还在想怎么在线算法切掉这题,所以一直拖着没发(这题也是需要换个思维去做的)

a_lc_检查边长度限制的路径是否存在(并查集离线处理)

标签:list   集中   lambda   one   数组   lis   for   长度   pre   

原文地址:https://www.cnblogs.com/wdt1/p/14163902.html

版权声明:完美者 发表于 2020-12-25 11:59:48。
转载请注明:a_lc_检查边长度限制的路径是否存在(并查集离线处理) | 完美导航

暂无评论

暂无评论...