[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[next]를 세팅해준다.

low[next]를 세팅한 뒤, low[next] > num[now] 인경우 critical connections으로 보고 정답 배열에 추가한다.

 

시간복잡도는 O(V+E). 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1192.%20Critical%20Connections%20in%20a%20Network.cpp