Kruskal adjust

q1

Given a graph and a minimum distance, determine if a path exists from source to target where edges exist only if the distance is less than or equal to threshold.
Follow-up: Instead of a given threshold, find the minimum threshold that allows reaching the target. Example A-->B (2), B-->C(3), A-->C(5), if source and target is A and C, answer would be 3.

for first part we can just dfs or bfs. We can also filter given edges that have weights bigger than threshold cuz its invalid edge

from collections import deque, defaultdict

def has_path_with_threshold(n, edges, source, target, threshold):
    # 1. Build the adjacency list, filtering out edges with weight > threshold
    # or  graph = [[] for _ in range(n)]
    graph = defaultdict(list)
    for u, v, w in edges:
        if w <= threshold:
            graph[u].append(v)
            graph[v].append(u)  # undirected graph

    # 2. BFS to see if target is reachable from source
    visited = set()
    queue = deque([source])

    while queue:
        node = queue.popleft()
        if node == target:
            return True
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
    return False

# Example usage:
edges = [(0, 1, 2), (1, 2, 3), (0, 2, 5)]
source, target = 0, 2
threshold = 3
print(has_path_with_threshold(3, edges, source, target, threshold))  # Output: True

the second part is quite tricky. I thought it is dijkstra but actually we wanna return min. threshold of edge that connects a complete path from source to target. It is not dijkstra which calculates minimum total path sum.

For this, we can actually use kruskal. But i thought kruskal is to make MST. but if we just change the alg a little, we notice as we are union finding and connecting the nodes (rmb edges are first sorted via increasing order of weights), once wei find the source and target have the same parent, then this edge that we have just union found and linked gives the minimum weight that connects target and source together.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu != pv:
            self.parent[pu] = pv

def minimumThreshold(n, edges, source, target):
    # edges: list of (u, v, w)
    edges.sort(key=lambda x: x[2])  # sort by weight
    uf = UnionFind(n)
    
    for u, v, w in edges:
        uf.union(u, v)
        if uf.find(source) == uf.find(target):
            return w  # minimum threshold reached

    return -1  # target unreachable

# Example usage:
n = 3
edges = [(0, 1, 2), (1, 2, 3), (0, 2, 5)]  # A=0, B=1, C=2
source, target = 0, 2
print(minimumThreshold(n, edges, source, target))  # Output: 3

complexity

for first part, graph takes e time but each bfs traversal takes e+ n. I thought its just n but actully bfs also checks each edge to find neighbours.

space is v+e for that graph, which is most dominant. Queue only stores v space

for second part, union find is close to o(e) but the sort takes e log e, which is the dominant time
for space, it takes o(v) where v is number of vertices