CF 106043F - Graph Problem

We are given a connected undirected weighted graph. Starting at vertex s and ending at vertex t, we may follow any walk, not necessarily a simple path. Vertices and edges may be revisited arbitrarily many times.

codeforcescompetitive-programming

CF 106043F - Graph Problem

Rating: -
Tags: -
Solve time: 1m 9s
Verified: yes

Solution

Problem Understanding

We are given a connected undirected weighted graph. Starting at vertex s and ending at vertex t, we may follow any walk, not necessarily a simple path. Vertices and edges may be revisited arbitrarily many times.

Every walk has a total weight, obtained by summing the weights of all traversed edges. We only care about that total modulo k.

The task is to determine how many distinct remainders modulo k can appear among all possible walks from s to t.

The graph can contain up to 10^5 vertices and 2·10^5 edges per test case. Any solution that tries to enumerate walks is hopeless, since even the number of simple paths can already be exponential. We need a structural characterization of all achievable path sums.

The most dangerous edge case is a tree. In a tree there is only one simple path between two vertices, but walks are still not unique because we may traverse an edge and immediately come back.

For example:

2 1 4 1 2
1 2 1

The direct walk has weight 1.

We may also do:

1 -> 2 -> 1 -> 2

whose weight is 3.

The achievable residues modulo 4 are {1,3}, so the answer is 2, not 1.

Another subtle case is when the graph contains cycles whose total weight is not compatible with k.

Consider:

k = 6
cycle weight = 4

Repeatedly inserting that cycle changes the remainder by 4 mod 6, producing only the subgroup generated by gcd(4,6)=2. A solution that assumes every cycle creates all residues would overcount.

A final edge case is k = 1. Every number is congruent to 0 mod 1, so the answer must always be 1.

Approaches

A brute force idea is to generate walks from s to t, compute their weights modulo k, and mark reachable residues. This immediately runs into trouble because the graph may contain cycles. The number of walks is infinite, and even restricting ourselves to short walks does not help because the graph size reaches 10^5.

The key observation is that all walks differ from one another only by inserted closed walks. If we know which weight changes can be produced by closed walks, then every s -> t walk is simply a fixed base value plus some combination of those changes.

Choose any spanning tree and let dist[v] be the tree-distance from the root to v.

For a non-tree edge (u,v,w), compare the tree path from the root to v with the route that goes from the root to u and then uses this edge. The discrepancy

dist[u] + w - dist[v]

measures how much weight can be injected into a walk by using that cycle.

Tree edges contribute another type of generator. Even in a pure tree, we may traverse an edge and immediately return. That changes the walk weight by exactly 2w.

All possible differences between two s -> t walks form an additive subgroup of the integers generated by:

2w                           for every edge
dist[u] + w - dist[v]        for every edge

Let

G = gcd(all generators above)

Every walk weight is congruent to

base + x·G

for some integer x.

Modulo k, the subgroup generated by G contains exactly

k / gcd(k, G)

distinct residues.

That value is the answer.

Approach Time Complexity Space Complexity Verdict
Brute Force Infinite / Exponential Unbounded Too slow
Optimal O(n + m) O(n + m) Accepted

Algorithm Walkthrough

  1. Build a spanning tree using DFS or BFS.
  2. While traversing the tree, compute dist[v], the total tree weight from the root to vertex v.
  3. Initialize G = 0.
  4. For every graph edge (u,v,w), update:
G = gcd(G, 2w)

This accounts for traversing an edge and immediately coming back. 5. For the same edge, update:

G = gcd(G, abs(dist[u] + w - dist[v]))

This captures the discrepancy created by cycles. 6. After all edges are processed, compute:

d = gcd(G, k)
  1. Output:
k / d

Why it works

The tree distances give a potential function. Every edge traversal can be written as a telescoping contribution plus a discrepancy term.

When a complete s -> t walk is expanded this way, the telescoping parts collapse to a fixed constant depending only on s and t. The only freedom comes from integer combinations of the discrepancy values and the 2w backtracking operations.

The set of all walk-weight differences is exactly the additive subgroup generated by those values. Any additive subgroup of the integers is generated by its gcd, which is G.

Modulo k, the reachable residues form the cyclic subgroup generated by G mod k. A cyclic subgroup generated by G has size k / gcd(k,G), giving the required count.

Python Solution

import sys
from math import gcd

input = sys.stdin.readline

def solve():
    t = int(input())

    for _ in range(t):
        n, m, k, s, tt = map(int, input().split())

        adj = [[] for _ in range(n)]
        edges = []

        for _ in range(m):
            u, v, w = map(int, input().split())
            u -= 1
            v -= 1

            adj[u].append((v, w))
            adj[v].append((u, w))
            edges.append((u, v, w))

        dist = [0] * n
        vis = [False] * n

        stack = [0]
        vis[0] = True

        while stack:
            u = stack.pop()

            for v, w in adj[u]:
                if not vis[v]:
                    vis[v] = True
                    dist[v] = dist[u] + w
                    stack.append(v)

        g = 0

        for u, v, w in edges:
            g = gcd(g, 2 * w)
            g = gcd(g, abs(dist[u] + w - dist[v]))

        print(k // gcd(k, g))

solve()

The DFS computes tree distances from an arbitrary root. The root choice does not matter because only gcd values are used later.

The first gcd update incorporates the ability to traverse an edge and immediately return. Without this term, trees would be handled incorrectly.

The second gcd update captures cycle discrepancies. Tree edges automatically contribute zero because for a tree edge we have:

dist[v] = dist[u] + w

and the expression becomes zero.

All arithmetic fits comfortably in 64-bit integers. Distances can reach roughly:

10^5 × 10^9 = 10^14

which is well within Python's integer range.

Worked Examples

Example 1

Input:

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

One possible DFS tree gives:

Vertex dist
1 0
2 1
3 5
4 3

Now process edges.

Edge 2w dist[u]+w-dist[v] Current G
1-4 (3) 6 0 6
1-2 (1) 2 0 2
2-4 (2) 4 0 2
2-3 (4) 8 0 2
3-4 (5) 10 7 1

Finally:

Quantity Value
G 1
gcd(G,k) 1
Answer 3

This confirms that all three residues modulo 3 are reachable.

Example 2

Input:

1
2 1 4 1 2
1 2 1

Distances:

Vertex dist
1 0
2 1

Edge processing:

Edge 2w discrepancy Current G
1-2 2 0 2

Final computation:

Quantity Value
G 2
gcd(G,k) 2
Answer 2

The reachable residues are {1,3}.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) One graph traversal and one pass over all edges
Space O(n + m) Adjacency list, distances, visited array

With n ≤ 10^5 and m ≤ 2·10^5, a linear solution easily fits within typical contest limits.

Test Cases

import sys
import io
from math import gcd

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

    input = sys.stdin.readline

    t = int(input())
    out = []

    for _ in range(t):
        n, m, k, s, tt = map(int, input().split())

        adj = [[] for _ in range(n)]
        edges = []

        for _ in range(m):
            u, v, w = map(int, input().split())
            u -= 1
            v -= 1

            adj[u].append((v, w))
            adj[v].append((u, w))
            edges.append((u, v, w))

        dist = [0] * n
        vis = [False] * n

        st = [0]
        vis[0] = True

        while st:
            u = st.pop()

            for v, w in adj[u]:
                if not vis[v]:
                    vis[v] = True
                    dist[v] = dist[u] + w
                    st.append(v)

        g = 0

        for u, v, w in edges:
            g = gcd(g, 2 * w)
            g = gcd(g, abs(dist[u] + w - dist[v]))

        out.append(str(k // gcd(k, g)))

    return "\n".join(out)

# sample
assert run(
"""1
4 5 3 1 4
1 4 3
1 2 1
2 4 2
2 3 4
3 4 5
"""
) == "3"

# single edge
assert run(
"""1
2 1 4 1 2
1 2 1
"""
) == "2"

# k = 1
assert run(
"""1
2 1 1 1 2
1 2 100
"""
) == "1"

# all weights zero
assert run(
"""1
3 2 7 1 3
1 2 0
2 3 0
"""
) == "1"

# cycle producing all residues modulo 5
assert run(
"""1
3 3 5 1 3
1 2 1
2 3 1
1 3 1
"""
) == "5"
Test input Expected output What it validates
Single edge, weight 1, k=4 2 Backtracking via 2w
k=1 1 Smallest modulus
All weights zero 1 Degenerate graph
Triangle with gcd 1 5 Full residue coverage
Official sample 3 General correctness

Edge Cases

Consider the tree:

1
2 1 4 1 2
1 2 1

A solution that only looks at cycles would conclude there is no freedom because the graph has no cycles. That is incorrect. The walk

1 -> 2 -> 1 -> 2

adds 2 to the total weight. Our algorithm explicitly inserts 2w into the gcd computation, producing G = 2 and the correct answer 2.

Now consider:

1
2 1 1 1 2
1 2 100

Every integer is congruent to 0 mod 1. The algorithm computes:

answer = 1 / gcd(1, G) = 1

which is the only possible result.

Finally, consider a graph whose cycle discrepancy gcd is already 1. Once G = 1, we have:

gcd(k, G) = 1

and the answer becomes k. The algorithm correctly recognizes that every residue modulo k can be produced.