CF 178B1 - Greedy Merchants
We are given a connected undirected graph representing cities and roads in the Roman Empire. Each merchant wants to transport goods between two cities.
Rating: 1600
Tags: -
Solve time: 2m 15s
Verified: yes
Solution
Problem Understanding
We are given a connected undirected graph representing cities and roads in the Roman Empire. Each merchant wants to transport goods between two cities. A road is considered important for a merchant if removing that single road disconnects the merchant’s warehouse city from the shop city.
For every query (s, l), we must count how many roads are critical for connectivity between s and l.
This is not asking for all bridges in the graph. A bridge only matters if it lies on every path between the two specific cities of the merchant. Some bridges may be completely unrelated to a given pair.
The graph has up to 10^5 vertices and edges, and there can also be 10^5 merchants. A solution that performs graph traversal per query is far too slow. Even an O(n) or O(m) computation for each merchant would lead to roughly 10^10 operations in the worst case.
The graph structure strongly suggests bridge decomposition. Removing non-bridge edges never disconnects the graph, so only bridges can possibly matter. The key question becomes:
How many bridges lie on the path between two cities?
That immediately points toward compressing the graph into bridge-connected components.
There are several edge cases that easily break naive implementations.
Consider a graph with no bridges:
1 - 2
| |
4 - 3
Input:
4 4
1 2
2 3
3 4
4 1
1
1 3
Output:
0
A careless approach that counts edges on one DFS tree path would incorrectly return 2, even though removing any single edge still leaves another route.
Now consider a pure tree:
1 - 2 - 3 - 4
Input:
4 3
1 2
2 3
3 4
1
1 4
Output:
3
Every edge is a bridge in a tree. Forgetting this special structure often causes undercounting if the implementation only marks articulation points instead of bridges.
Another subtle case appears when both cities belong to the same 2-edge-connected component.
1 - 2 - 3
\ /
---
Input:
3 3
1 2
2 3
3 1
1
1 2
Output:
0
Even though there are edges on DFS paths between the nodes, none are important because cycles provide alternative routes.
The final tricky situation is when the graph contains several cyclic regions connected by bridges:
cycle -- bridge -- cycle -- bridge -- cycle
Only the bridges between the compressed components matter. Counting internal edges inside cycles is incorrect.
Approaches
The brute-force solution follows the definition directly.
For every merchant (s, l), we try removing each edge one at a time. After removing an edge, we run DFS or BFS to check whether s can still reach l. If not, that edge is important for the merchant.
This works because the definition itself asks whether connectivity survives after deleting one road.
The complexity becomes enormous. There are m candidate edges, and each connectivity check costs O(n + m). Repeating this for k merchants gives:
O(k * m * (n + m))
With all limits near 10^5, this is completely impossible.
The first improvement is realizing that only bridges matter. If an edge belongs to a cycle, removing it cannot disconnect any pair of cities because another route exists around the cycle.
So the problem reduces to:
For each query, count how many bridges separate the two cities.
This transforms the graph completely.
If we remove all bridges, the remaining connected components are maximal regions where every pair of vertices still has an alternative path after deleting any single edge. Inside such a component, no road is important for any internal pair.
We compress every such component into a single node. Every bridge becomes an edge between components.
A crucial property appears here:
The compressed graph is a tree.
Why? Any cycle in the compressed graph would imply the corresponding bridge was actually not a bridge.
Now the original question becomes much simpler:
For two cities u and v, find their component IDs in the bridge-tree. The answer equals the number of edges on the tree path between those two components.
Tree distance can be answered efficiently using Lowest Common Ancestor, or LCA.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(k * m * (n + m)) |
O(n + m) |
Too slow |
| Optimal | O((n + m + k) log n) |
O(n + m) |
Accepted |
Algorithm Walkthrough
- Run Tarjan DFS to find all bridges in the graph.
We maintain discovery times tin[u] and low-link values low[u].
An edge (u, v) is a bridge if:
$low[v] > tin[u]$
This means the subtree rooted at v cannot reach u or any ancestor of u using a back edge.
2. Remove all bridge edges conceptually and build connected components.
We run DFS again, but never cross a bridge. Every traversal marks vertices belonging to the same 2-edge-connected component. 3. Build the bridge-tree.
Every component becomes one node. For every bridge connecting original vertices u and v, add an edge between comp[u] and comp[v].
The resulting structure is always a tree. 4. Preprocess Lowest Common Ancestor on the bridge-tree.
We root the tree arbitrarily, usually at component 0.
During DFS, compute:
depth[node]
up[node][j], the 2^j-th ancestor.
5. Answer each merchant query.
Suppose the cities belong to components a and b.
The number of important roads equals the distance between a and b in the bridge-tree:
$dist(a,b)=depth[a]+depth[b]-2\cdot depth[lca(a,b)]$
Each edge on this path corresponds to exactly one bridge in the original graph.
Why it works
After removing all bridges, each remaining component has at least two disjoint paths between every pair of vertices. No single edge inside such a component can disconnect any internal pair.
Every bridge separates the graph into exactly two parts. If two cities lie on opposite sides of that bridge, the bridge is unavoidable and must be counted.
Compressing components transforms the graph into a tree where every edge corresponds to exactly one bridge. Any path between two components in a tree is unique, so the number of important roads equals the number of bridge edges on that unique path.
Because LCA computes tree distances correctly, every query answer is correct.
Python Solution
import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
LOG = 20
def solve():
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
edges = []
for i in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
edges.append((u, v))
graph[u].append((v, i))
graph[v].append((u, i))
tin = [-1] * n
low = [0] * n
timer = 0
is_bridge = [False] * m
def dfs_bridge(u, parent_edge):
nonlocal timer
tin[u] = low[u] = timer
timer += 1
for v, eid in graph[u]:
if eid == parent_edge:
continue
if tin[v] != -1:
low[u] = min(low[u], tin[v])
else:
dfs_bridge(v, eid)
low[u] = min(low[u], low[v])
if low[v] > tin[u]:
is_bridge[eid] = True
dfs_bridge(0, -1)
comp = [-1] * n
comp_cnt = 0
def dfs_comp(u, cid):
comp[u] = cid
for v, eid in graph[u]:
if comp[v] != -1 or is_bridge[eid]:
continue
dfs_comp(v, cid)
for i in range(n):
if comp[i] == -1:
dfs_comp(i, comp_cnt)
comp_cnt += 1
tree = [[] for _ in range(comp_cnt)]
for eid, (u, v) in enumerate(edges):
cu = comp[u]
cv = comp[v]
if cu != cv:
tree[cu].append(cv)
tree[cv].append(cu)
up = [[0] * LOG for _ in range(comp_cnt)]
depth = [0] * comp_cnt
def dfs_lca(u, p):
up[u][0] = p
for j in range(1, LOG):
up[u][j] = up[up[u][j - 1]][j - 1]
for v in tree[u]:
if v == p:
continue
depth[v] = depth[u] + 1
dfs_lca(v, u)
dfs_lca(0, 0)
def lca(a, b):
if depth[a] < depth[b]:
a, b = b, a
diff = depth[a] - depth[b]
for j in range(LOG):
if diff & (1 << j):
a = up[a][j]
if a == b:
return a
for j in range(LOG - 1, -1, -1):
if up[a][j] != up[b][j]:
a = up[a][j]
b = up[b][j]
return up[a][0]
k = map(int, input().split())
import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
LOG = 20
def solve():
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
edges = []
for i in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
edges.append((u, v))
graph[u].append((v, i))
graph[v].append((u, i))
tin = [-1] * n
low = [0] * n
timer = 0
is_bridge = [False] * m
def dfs_bridge(u, parent_edge):
nonlocal timer
tin[u] = low[u] = timer
timer += 1
for v, eid in graph[u]:
if eid == parent_edge:
continue
if tin[v] != -1:
low[u] = min(low[u], tin[v])
else:
dfs_bridge(v, eid)
low[u] = min(low[u], low[v])
if low[v] > tin[u]:
is_bridge[eid] = True
dfs_bridge(0, -1)
comp = [-1] * n
comp_cnt = 0
def dfs_comp(u, cid):
comp[u] = cid
for v, eid in graph[u]:
if comp[v] != -1:
continue
if is_bridge[eid]:
continue
dfs_comp(v, cid)
for i in range(n):
if comp[i] == -1:
dfs_comp(i, comp_cnt)
comp_cnt += 1
tree = [[] for _ in range(comp_cnt)]
for eid, (u, v) in enumerate(edges):
cu = comp[u]
cv = comp[v]
if cu != cv:
tree[cu].append(cv)
tree[cv].append(cu)
up = [[0] * LOG for _ in range(comp_cnt)]
depth = [0] * comp_cnt
def dfs_lca(u, p):
up[u][0] = p
for j in range(1, LOG):
up[u][j] = up[up[u][j - 1]][j - 1]
for v in tree[u]:
if v == p:
continue
depth[v] = depth[u] + 1
dfs_lca(v, u)
dfs_lca(0, 0)
def lca(a, b):
if depth[a] < depth[b]:
a, b = b, a
diff = depth[a] - depth[b]
for j in range(LOG):
if diff & (1 << j):
a = up[a][j]
if a == b:
return a
for j in range(LOG - 1, -1, -1):
if up[a][j] != up[b][j]:
a = up[a][j]
b = up[b][j]
return up[a][0]
k = int(input())
out = []
for _ in range(k):
s, l = map(int, input().split())
s -= 1
l -= 1
a = comp[s]
b = comp[l]
c = lca(a, b)
ans = depth[a] + depth[b] - 2 * depth[c]
out.append(str(ans))
print("\n".join(out))
solve()
The first DFS computes bridges using Tarjan’s low-link technique. The subtle part is distinguishing tree edges from back edges. We skip only the exact parent edge by ID, not merely the parent vertex. This matters because undirected graphs revisit vertices through multiple edges during DFS traversal.
The second DFS assigns component IDs while ignoring bridges. Every maximal region connected without bridges becomes one compressed node.
The bridge-tree construction is straightforward because every bridge connects two different components. Non-bridge edges stay inside the same component and are ignored.
The LCA preprocessing uses binary lifting. Since the compressed graph is a tree, the distance formula directly gives the number of bridges between two components.
A common implementation mistake is forgetting that the compressed graph may contain only one component. In that case, the tree has one node and every query answer is zero. The code handles this naturally.
Another subtle detail is recursion depth. With 10^5 vertices, Python’s default recursion limit is too small, so we raise it significantly.
Worked Examples
Sample 1
Input:
7 8
1 2
2 3
3 4
4 5
5 6
5 7
3 5
4 7
4
1 5
2 4
2 6
4 7
The bridges are:
1-2
2-3
5-6
Everything else belongs to one cyclic component.
Compressed tree:
C0 -- C1 -- C2 -- C3
Where:
C0 = {1}
C1 = {2}
C2 = {3,4,5,7}
C3 = {6}
| Query | Components | Tree Distance | Answer |
|---|---|---|---|
| 1 5 | C0 to C2 | 2 | 2 |
| 2 4 | C1 to C2 | 1 | 1 |
| 2 6 | C1 to C3 | 2 | 2 |
| 4 7 | C2 to C2 | 0 | 0 |
This example demonstrates the central idea of the solution. Internal movement inside a component never crosses a bridge, so only transitions between components contribute to the answer.
Custom Example
Input:
5 5
1 2
2 3
3 1
3 4
4 5
3
1 2
1 4
1 5
The graph contains a triangle plus a chain.
Bridges:
3-4
4-5
Compressed tree:
TriangleComponent -- A -- B
| Query | Components | LCA | Distance | Answer |
|---|---|---|---|---|
| 1 2 | same | same | 0 | 0 |
| 1 4 | triangle to A | triangle | 1 | 1 |
| 1 5 | triangle to B | triangle | 2 | 2 |
This trace confirms that cycles eliminate all internal important roads, while chains contribute exactly one important road per bridge crossed.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O((n + m + k) log n) |
Bridge DFS, component DFS, and tree construction are linear, each query uses LCA |
| Space | O(n + m) |
Graph storage, bridge arrays, component arrays, and binary lifting tables |
With 10^5 vertices, edges, and queries, linear preprocessing plus logarithmic query handling easily fits within the limits. The binary lifting table has roughly 20 * 10^5 integers, which is well within the memory bound.
Test Cases
import sys
import io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline
LOG = 20
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
edges = []
for i in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
edges.append((u, v))
graph[u].append((v, i))
graph[v].append((u, i))
tin = [-1] * n
low = [0] * n
timer = 0
is_bridge = [False] * m
def dfs_bridge(u, pe):
nonlocal timer
tin[u] = low[u] = timer
timer += 1
for v, eid in graph[u]:
if eid == pe:
continue
if tin[v] != -1:
low[u] = min(low[u], tin[v])
else:
dfs_bridge(v, eid)
low[u] = min(low[u], low[v])
if low[v] > tin[u]:
is_bridge[eid] = True
dfs_bridge(0, -1)
comp = [-1] * n
cid = 0
def dfs_comp(u, c):
comp[u] = c
for v, eid in graph[u]:
if comp[v] != -1 or is_bridge[eid]:
continue
dfs_comp(v, c)
for i in range(n):
if comp[i] == -1:
dfs_comp(i, cid)
cid += 1
tree = [[] for _ in range(cid)]
for eid, (u, v) in enumerate(edges):
cu = comp[u]
cv = comp[v]
if cu != cv:
tree[cu].append(cv)
tree[cv].append(cu)
up = [[0] * LOG for _ in range(cid)]
depth = [0] * cid
def dfs(u, p):
up[u][0] = p
for j in range(1, LOG):
up[u][j] = up[up[u][j - 1]][j - 1]
for v in tree[u]:
if v == p:
continue
depth[v] = depth[u] + 1
dfs(v, u)
dfs(0, 0)
def lca(a, b):
if depth[a] < depth[b]:
a, b = b, a
diff = depth[a] - depth[b]
for j in range(LOG):
if diff & (1 << j):
a = up[a][j]
if a == b:
return a
for j in range(LOG - 1, -1, -1):
if up[a][j] != up[b][j]:
a = up[a][j]
b = up[b][j]
return up[a][0]
k = int(input())
ans = []
for _ in range(k):
s, l = map(int, input().split())
s -= 1
l -= 1
a = comp[s]
b = comp[l]
c = lca(a, b)
ans.append(str(depth[a] + depth[b] - 2 * depth[c]))
return "\n".join(ans)
# sample 1
assert run(
"""7 8
1 2
2 3
3 4
4 5
5 6
5 7
3 5
4 7
4
1 5
2 4
2 6
4 7
"""
) == """2
1
2
0"""
# single node
assert run(
"""1 0
1
1 1
"""
) == "0"
# pure cycle
assert run(
"""4 4
1 2
2 3
3 4
4 1
2
1 3
2 4
"""
) == """0
0"""
# pure tree
assert run(
"""5 4
1 2
2 3
3 4
4 5
2
1 5
2 4
"""
) == """4
2"""
# cycle connected to chain
assert run(
"""5 5
1 2
2 3
3 1
3 4
4 5
3
1 2
1 4
1 5
"""
) == """0
1
2"""
| Test input | Expected output | What it validates |
|---|---|---|
| Single node graph | 0 |
Minimum boundary case |
| Pure cycle | All zeros | Non-bridge edges never matter |
| Pure tree | Path length | Every edge is a bridge |
| Cycle plus chain | Mixed answers | Correct bridge compression |
Edge Cases
Consider a graph with no bridges:
4 4
1 2
2 3
3 4
4 1
1
1 3
The bridge DFS marks no edges as bridges. The entire graph becomes one component. Both query vertices map to the same compressed node, so the LCA distance is zero.
Output:
0
Now consider a tree:
4 3
1 2
2 3
3 4
1
1 4
Every edge satisfies:
$low[v] > tin[u]$
So every edge becomes part of the bridge-tree. The compressed graph is identical to the original tree. The path from 1 to 4 contains three edges, so the answer is 3.
Finally, consider a graph where both query vertices lie inside one cyclic component:
5 5
1 2
2 3
3 1
3 4
4 5
1
1 2
The triangle forms one component. The query cities map to the same compressed node even though they are different original vertices. Since the tree distance is zero, the algorithm correctly outputs:
0
This case confirms that the algorithm counts only bridges, not arbitrary path edges.