tarjan1 [leetcode][1192] Critical Connections in a Network 문제 : https://leetcode.com/problems/critical-connections-in-a-network/ tarjan 알고리즘으로 풀었다. dfs로 정점들을 방문하면서 해당 정점을 방문한 순번(num)과 하나의 간선만으로 갈 수 있는 정점들 중 가장 작은 정점(low)을 저장하는 배열들을 저장한다. low 저장하는 조건. now = 현재 탐색중인 정점 next = now에서 방문할 다음 정점 1. next 정점을 이미 방문한 경우(back edge) : low[now] = min(low[now], low[next]) 2. next 정점을 아직 방문하지 않은 경우 : low[now] = min(low[now], num[next]). 2번인 경우 next 정점을 dfs로 방문하면서 low.. 2019. 9. 23. 이전 1 다음