## D - Hidden Weights Editorial by en_translator

For each connected component of the graph, once the value to be written on any vertex in it is fixed, all the values to be written is uniquely determined. This is because, once you determine the value for a vertex, the value for adjacent vertices are also determined in a chain. Thus, the problem can be solved by inspecting vertices one by one, and if the current vertex does not have a value assigned, set an arbitrary value (like \(0\)) to it and determine the values for all the other connected vertices.

This kind of process can be implemented as a **Depth-First Search (DFS)** or **Breadth-First Search (BFS)**. The following sample code employs DFS. The time complexity is \(O(N+M)\).

```
# Read the input
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
u, v, w = map(int, input().split())
u -= 1
v -= 1
G[u].append((v, w))
G[v].append((u, -w))
visited = [False] * N # Whether the values are determined
ans = [0] * N # The values to write
for i in range(N):
# Skip if the value is already determined
if visited[i]:
continue
# Set the value for vertex i to 0, and start searching
st = [i]
visited[i] = True
while st:
# Currently at vertex u
u = st.pop()
# Inspect vertex v adjacent to vertex u
for v, w in G[u]:
if not visited[v]:
# If the value for vertex v is undetermined, determine the value so that it is consistent with that for vertex u
visited[v] = True
ans[v] = ans[u] + w
st.append(v)
print(*ans)
```

posted:

last update: