[백준] 14267번: 회사 문화 1

initial

I thought why is this gold 4? We can just do dfs for each iter of for loop but to mark the child nodes. But we get runtime cuz it could be up to 100,000 iterations, not to mention the recursive dfs v+e time complexity.

initial runtime code but correct:

from collections import defaultdict
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
lst = list(map(int, input().split()))
graph = defaultdict(list)

for i in range(1, n + 1):
    if lst[i-1] == -1:
        continue
    graph[lst[i-1]].append(i)

ans = [0 for _ in range(n + 1)]

def dfs(node, no):
    global ans
    for child in graph[node]:
        if child < node:
            continue
        ans[child] += no
        dfs(child, no)

for _ in range(m):
    node, no = map(int, input().split())
    ans[node]+=no
    dfs(node, no)
    
print(*ans[1:])

To optimise, we should runt dfs for each input. We mark the nodes with praises initially and when we do dfs, we add the parent’s value to the child’s value like inheritance. So if we do dfs(1), it will go to all the children and spread out while adding paren’ts value to child node and continuing recursively.

solution

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
lst = list(map(int, input().split()))
graph = defaultdict(list)

for i in range(1, n + 1):
    if lst[i-1] == -1:
        continue
    graph[lst[i-1]].append(i)

ans = [0 for _ in range(n + 1)]

def dfs(node):
    global ans
    for child in graph[node]:
        ans[child] += ans[node]
        dfs(child)

for _ in range(m):
    node, no = map(int, input().split())
    ans[node] += no

dfs(1)
print(*ans[1:])

complexity

dfs o(v+e)

The time complexity of the DFS traversal in the given code is O(n + m), where n is the number of nodes in the graph and m is the number of queries.
The loop that iterates through the nodes has a time complexity of O(n).
The loop that iterates through the queries has a time complexity of O(m).
The DFS traversal visits each node once and each query once.
Space Complexity:

The space complexity of the given code is O(n).
The graph dictionary stores the adjacency list representation of the graph, and its space complexity is O(n) in the worst case.
The ans list stores the final answer for each node, and its space complexity is also O(n).
Note: The sys.setrecursionlimit(10**6) line is setting the recursion limit to a relatively high value, which is fine for most cases. However, keep in mind that using recursion for deep traversals in Python might lead to a maximum recursion depth exceeded error in certain cases. The iterative version of DFS can be used to avoid this issue.