728x90 반응형 강한 연결 요소1 강한 연결 요소 (Strongly Connected Component) 강한 연결 요소 (Strongly Connected Component)는 SCC라고 불리는 알고리즘 입니다. 유향 그래프에서 특정 노드에서 다른 노드들을 걸쳐 다시 특정노드로 돌아올 수 있으면, 노드들이 강하게 연결되어 있다 라고 합니다. DFS를 배우셨다면, 조금 쉽게 이해하실 수 있을거 같습니다. ex) https://www.acmicpc.net/problem/26146 26146번: 즉흥 여행 (Easy) 1번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지만, 2번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지 않으므로, 답은 No가 된다. www.acmicpc.net 1에서 2를 걸쳐 3으로 갔다가 다시 1로 돌아올 수 있음, 1에서 4로 갔다가 다시 돌아올 수 있.. 2023. 1. 26. 이전 1 다음 728x90 반응형
