문제

• 
• 시간 제한: 2초
• 메모리 제한: 512MB

Problem Analysis

Naive 하게 DFS로 모든 경우의 수를 조사하면 만나는 시간을 구하는 데만 O( V*(V+E) )이다. 이는, 시작 지점에서 도시 u로 가는 시간을 새로 갱신하면, u와 인접한 도시들도 다시 갱신해 주어야 하기 때문에 발생하는 문제이다. 이러한 방법 대신, 도시 u로 가는 시간을 한 번에 다 구한 뒤에, 이후에 u와 인접한 도시들을 갱신해 주는 것이 효율적일 것이다.

Algorithm

Topological Order 순으로 각 도시와 인접한 도시들의 도착시간을 구한다. 이후, 이를 역추적하여, 도로의 수를 센다. 구체적인 순서는 다음과 같다.

1. Topological Sort(DFS)

2. stack을 pop하며, 해당 도시(u)에서 갈 수 있는 인접 도시들(v)의 도착시간을 갱신해 준다.

• v로 가는 최대 도착시간에 해당한다면
  • 해당 도로를 (v의 max를 만드는 도로 개수)+1을 해준다.
  • u를 (v의 max를 만드는 이전 도시)에 추가해 준다.

3. 도착 도시에서 (Max를 만드는 이전 도시)로 추적하면서 도로의 개수 총합을 구해준다.

Data Structure

• stack topological_order: topological order를 저장
• max_dist[]: 각 도시의 도착시간
• num_of_max_edges[]: 각 도시의 도착시간을 최대로 만드는 이전 도시와 현재 도시 간의 도로 수
• prev_node_max[]: 각 도시의 도착시간을 최대로 만드는 이전 도시

결과

Other

시간 복잡도는, 도착시간 구하는 데 Topological Sort에 O(n+m), Topological order로 다시 인접 도시를 갱신하는데 O(n+m)이 걸리고, 역추적 하는데 O(n)이 걸린다.