update) 2019.11.02 00:29
겨울방학 1주차 공부 일지
작성일
|
In
Study
[그래프] 단절선
작성일
|
In
Hard-Algorithm
단절선이란?
하나의 컴포넌트(connected component)로 구성되어 있는 그래프에서 특정 간선을 제거할 때, 컴포넌트의 개수가 증가하는 간선을 단절선
이라고 합니다.
쉽게 말해, 어떤 간선을 제거했을 때, 그래프가 둘 이상으로 나뉘게 된다면 그 간선은 단절선입니다.
[그래프] 단절점
작성일
|
In
Hard-Algorithm
단절점이란?
하나의 컴포넌트(connected component)로 구성되어 있는 그래프에서 특정 정점을 제거할 때, 컴포넌트의 개수가 증가하는 정점을 단절점
이라고 합니다.
쉽게 말해, 어떤 정점을 제거했을 때 그래프가 둘 이상으로 나뉘게 된다면 그 정점은 단절점입니다.
백준10937 두부 모판 자르기
작성일
|
In
KOI
백준1693 트리 색칠하기
작성일
|
In
PS
백준10840 구간 성분
작성일
|
In
KOI
[그래프] SCC - Tarjan
작성일
|
In
Hard-Algorithm
SCC를 구하는 또 다른 알고리즘인 Tarjan’s Algorithm을 알아봅시다.
[그래프] SCC - Kosaraju
작성일
|
In
Hard-Algorithm
SCC를 구하는 알고리즘 중 Kosaraju’s Algorithm을 알아봅시다.
[그래프] SCC 개요
작성일
|
In
Hard-Algorithm
SCC는 Strongly Connected Component의 약자로, 강한 연결 요소를 의미합니다.
어떤 강한 연결 요소 안에 있는 정점은, 서로 이동이 가능합니다. 다시 말해, 같은 강한 연결 요소에 있다면, 갈 수 있음을 의미합니다. 방향 그래프에서 정의됩니다.
SCC알고리즘은 그래프를 Strongly Conneted한 서브 그래프로 나누는 알고리즘입니다.