[BOJ2150] Strongly Connected Component
[BOJ2150] Strongly Connected Component 문제 링크 문제 설명 문제 설명은 따로 없다. SCC를 찾아서 그 안에 있는 정점들을 정렬하여 출력하고 마지막에 -1을 붙혀주면 된다. SCC(강한연결성분)란? ...
최근 포스트
[알고리즘설계]DFS를 이용한 위상정렬
[알고리즘설계] DFS를 이용한 위상정렬 코드 리뷰 접점과 간선의 정보를 통해 방향그래프를 만든다. 위상정렬을 하려면 방향그래프에 사이클이 없어야 한다. 한번도 방문하지 않은 정점은 white , 정점에 인접한 정점들을 모두 방...
[자료구조]더미노드를 활용한 정렬기능이 추가된 연결리스트
[자료구조]더미노드를 활용한 정렬기능이 추가된 연결리스트 자료구조의 틀 새 노드를 추가할 시, 리스트의 head 부분으로 저장을 시작한다. 장점은 리스트의 마지막을 가리키는 포인터변수 tail이 필요 없다. 단점이라고 말하기는 ...
[알고리즘설계]BFS를 이용한 위상정렬
[알고리즘설계] BFS를 이용한 위상정렬 코드 리뷰 접점과 간선의 정보를 통해 방향그래프를 만든다. 위상정렬을 하려면 방향그래프에 사이클이 없어야 한다. 또한 방향그래프에 사이클이 없으면 위상정렬을 할 수 있으므로, 둘은 동치관...
[BOJ1707] 이분 그래프
[BOJ1707] 이분 그래프 문제 링크 문제 설명 이분 그래프란 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때의 그래프를 말한다. 쉽게 말해서, 인접한 정점끼리는 서로 다른 색으로 ...