CF 103145K - City

We are given a weighted undirected graph where each edge represents a road between two cities, and each road has a strength value. A global attack parameter $x$ removes every road whose strength is strictly less than $x$.

codeforcescompetitive-programming

CF 103145K - City

Rating: -
Tags: -
Solve time: 48s
Verified: yes

Solution

Problem Understanding

We are given a weighted undirected graph where each edge represents a road between two cities, and each road has a strength value. A global attack parameter $x$ removes every road whose strength is strictly less than $x$. After this removal, only edges with strength at least $x$ remain, and we consider connectivity in the remaining graph.

Each query asks for the number of pairs of cities that are still connected after such an attack. A pair $(u, v)$ is counted if there exists a path between them using only edges whose strengths are at least the query value, meaning the path survives the destruction process.

The output is therefore not a simple connectivity check, but a global count of reachable pairs in a dynamically filtered graph.

The constraints immediately rule out recomputing connectivity per query. With $n$ up to $10^5$, $m$ and $Q$ up to $2 \cdot 10^5$, and up to 10 test cases, any approach that rebuilds a graph or runs BFS or DFS per query would lead to roughly $O(Q \cdot (n + m))$, which is far beyond feasible limits.

A subtle edge case appears when all edges have small strengths but queries are large. In that case, the graph becomes fully disconnected, and the answer must be zero for every pair. Conversely, if all edges are large and queries are small, the entire graph stays connected and the answer becomes $\frac{n(n-1)}{2}$. A naive solution that recomputes components per query may still pass small tests but will fail due to time complexity.

Approaches

The brute-force idea is straightforward: for each query $p_i$, construct the subgraph consisting only of edges with strength at least $p_i$, run a DFS or union-find to compute connected components, and then count pairs inside each component using the formula $s \cdot (s-1) / 2$, where $s$ is the component size. This is correct because connectivity in an undirected graph partitions nodes into disjoint components, and every pair inside a component is reachable.

However, rebuilding the graph or re-running connectivity from scratch for each query repeats almost the entire computation $Q$ times. In the worst case, this becomes $O(Q \cdot (n + m))$, which is on the order of $10^{10}$ operations, far beyond any practical limit.

The key observation is that connectivity only increases as we relax the threshold. If we process edges in decreasing order of strength, we can gradually build the graph, and connectivity evolves monotonically. Instead of recomputing from scratch for each query, we maintain a dynamic union-find structure that supports incremental merging of components.

We sort edges by strength descending and process queries in descending order as well. As we lower the threshold from large to small, we keep adding edges that become active. For each query, once all edges with strength at least that query are added, the union-find structure exactly represents the required graph. We can maintain the total number of connected pairs incrementally: when two components of sizes $a$ and $b$ merge, the number of newly connected pairs increases by $a \cdot b$.

This transforms repeated graph reconstruction into a single sweep with amortized near-constant union operations.

Approach Time Complexity Space Complexity Verdict
Brute Force $O(Q(n + m))$ $O(n + m)$ Too slow
Optimal (DSU sweep) $O((n + m + Q)\log(n + m))$ $O(n + m)$ Accepted

Algorithm Walkthrough

We process both edges and queries in a unified descending order of strength and threshold.

  1. Sort all edges by strength in decreasing order. This ensures that when we process an edge, all stronger edges have already been considered, so the current structure represents exactly the graph induced by edges above the current strength level.
  2. Sort queries by their threshold value in decreasing order while keeping track of their original indices. This allows us to answer queries in a single pass while restoring the output order later.
  3. Initialize a Disjoint Set Union structure where each city starts as its own component of size 1. Also initialize a variable that tracks the number of reachable pairs, initially zero since no edges exist.
  4. Iterate over queries from highest threshold to lowest. For each query value $p$, before answering it, insert all edges whose strength is at least $p$ and have not yet been processed.
  5. When inserting an edge between two components of sizes $a$ and $b$, check whether they are already connected. If not, merging them increases the number of reachable pairs by $a \cdot b$. This works because every node in one component becomes reachable from every node in the other component after the merge.
  6. After all applicable edges are added, the current DSU state exactly represents the graph after removing all edges weaker than $p$. Store the current reachable-pairs count as the answer for this query.
  7. Repeat until all queries are processed, then restore answers in original order.

The correctness relies on the fact that each edge is considered exactly once, and each union operation permanently merges components, so later queries only refine the threshold downward without invalidating earlier merges.

Why it works

At any moment during the sweep, the DSU represents the graph formed by all edges with strength at least the current processing threshold. This is an invariant maintained by processing edges in descending order. Since connectivity in an undirected graph is fully captured by its connected components, every reachable pair must lie within a DSU component.

When two components merge, every pair across them becomes newly connected, and no previously counted pair is ever lost because connectivity only grows as more edges are added. Therefore, the running sum of cross-component pairs exactly matches the number of reachable pairs for the current threshold.

Python Solution

import sys
input = sys.stdin.readline

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return 0
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return self.size[a] * self.size[b] - self.size[b] * (self.size[a] - self.size[b])

def solve():
    T = int(input())
    for _ in range(T):
        n, m, q = map(int, input().split())
        edges = []
        for _ in range(m):
            x, y, k = map(int, input().split())
            edges.append((k, x - 1, y - 1))

        queries = []
        for i in range(q):
            p = int(input())
            queries.append((p, i))

        edges.sort(reverse=True)
        queries.sort(reverse=True)

        dsu = DSU(n)
        ans = [0] * q
        total = 0

        j = 0
        for p, idx in queries:
            while j < m and edges[j][0] >= p:
                k, u, v = edges[j]
                u_root = dsu.find(u)
                v_root = dsu.find(v)
                if u_root != v_root:
                    total += dsu.size[u_root] * dsu.size[v_root]
                    dsu.parent[v_root] = u_root
                    dsu.size[u_root] += dsu.size[v_root]
                j += 1
            ans[idx] = total

        print("\n".join(map(str, ans)))

if __name__ == "__main__":
    solve()

The DSU is used to maintain connected components as edges are activated. The crucial implementation detail is that we never recompute connectivity from scratch; instead, we only merge components and maintain a running total of cross-component pairs. The pointer $j$ ensures each edge is processed once, making the sweep linear after sorting.

A subtle point is that we must update the answer after processing all edges with strength at least $p$, not before, since queries are inclusive thresholds.

Worked Examples

Consider a small graph:

Input:

1
4 4 3
1 2 5
2 3 3
3 4 2
1 4 1
5
3
2

We process edges sorted by strength: (5), (3), (2), (1). Queries are (5), (3), (2).

Trace

Query Activated edges DSU components Reachable pairs
5 (1-2) {1,2},{3},{4} 1
3 (1-2),(2-3) {1,2,3},{4} 3
2 (1-2),(2-3),(3-4) {1,2,3,4} 6

This shows how connectivity grows monotonically as the threshold decreases.

The trace confirms that each query only depends on a prefix of the sorted edge list, matching the sweep-line interpretation.

Complexity Analysis

Measure Complexity Explanation
Time $O((n + m + Q)\log(n + m))$ sorting edges and queries dominates, DSU operations are nearly constant amortized
Space $O(n + m + Q)$ storage for DSU, edges, and query bookkeeping

The constraints allow up to $2 \cdot 10^5$ edges and queries per test case, so the sorting plus linear sweep easily fits within time limits across all test cases.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    class DSU:
        def __init__(self, n):
            self.parent = list(range(n))
            self.size = [1] * n

        def find(self, x):
            while self.parent[x] != x:
                self.parent[x] = self.parent[self.parent[x]]
                x = self.parent[x]
            return x

    def solve():
        T = int(input())
        for _ in range(T):
            n, m, q = map(int, input().split())
            edges = []
            for _ in range(m):
                x, y, k = map(int, input().split())
                edges.append((k, x - 1, y - 1))

            queries = []
            for i in range(q):
                p = int(input())
                queries.append((p, i))

            edges.sort(reverse=True)
            queries.sort(reverse=True)

            dsu = DSU(n)
            ans = [0] * q
            total = 0

            j = 0
            for p, idx in queries:
                while j < m and edges[j][0] >= p:
                    k, u, v = edges[j]
                    u_root = dsu.find(u)
                    v_root = dsu.find(v)
                    if u_root != v_root:
                        total += dsu.size[u_root] * dsu.size[v_root]
                        dsu.parent[v_root] = u_root
                        dsu.size[u_root] += dsu.size[v_root]
                    j += 1
                ans[idx] = total

            print("\n".join(map(str, ans)))

    return ""

# provided samples
# assert run("...") == "..."

# custom tests

# 1. minimum size
assert run("""1
2 1 1
1 2 5
3
""") == "1\n"

# 2. disconnected graph
assert run("""1
3 0 2
1
10
""") == "0\n0\n"

# 3. fully connected high strength
assert run("""1
4 3 2
1 2 10
2 3 10
3 4 10
1
10
""") == "6\n6\n"
Test input Expected output What it validates
2 nodes single edge 1 minimal connectivity case
no edges 0,0 fully disconnected handling
all strong edges 6,6 full connectivity stability

Edge Cases

One important edge case is when there are no edges at all. The DSU never performs any union, so every query should correctly return zero reachable pairs. For example, with $n = 5$, $m = 0$, any number of queries must all output zero. The algorithm handles this naturally because the sweep loop never activates any edge, and the total remains unchanged.

Another case is when all queries are larger than any edge weight. Since we process edges in descending order and only activate edges with strength at least the query, no edge will ever be included. The DSU remains in its initial state, so every answer is zero.

A final case is when all edges are above all query thresholds. Then all edges are merged before the first query is answered, producing a single connected component. The DSU accumulates all pair contributions exactly once, and every query correctly returns $n(n-1)/2$, demonstrating stability across repeated queries with identical or smaller thresholds.