강한 연결 요소

[백준 4013] ATM C++

4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 강한 연결 요소, 다이나믹 프로그래밍 처음 풀어보는 플레2 문제였다. 풀려서 기분이 매우 좋았음 우선 모든 정점들을 dfs로 순회하며 각 정점의 SCC를 구해줬다. SCC를 구하면서 해당 SCC에 속하는 현금의 양 + 해당 SCC에 레스토랑이 있는지 판단해 주었다. 구한 SCC를 통해서 SCC 그래프를 만들어 주었다. -> make_sccgraph() 이제 DP문제로 바뀌게 되었다. 시작점의 SCC에서 출발해, 레스토랑이 있는 SCC까지의 거리의 ..

[백준 4196] 도미노 C++

4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 강한 연결 요소 1. 문제 해결 아이디어 강한 연결 요소 (SCC) - 타잔 알고리즘 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이.. hyeo-noo.tistory.com 타잔 알고리즘을 사용해서 풀었다. 개인적으로 코사라주보다 직관적이..

[백준 2150] Strongly Connected Component C++

2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 강한 연결 요소 ㅈㅎㄱ 교수님의 알고리즘 수업에서 강한 연결 요소 문제를 해결하기 위한 코사라주 알고리즘을 배우고 이를 적용하는 문제를 풀어보았다. 1. 문제 해결 아이디어 위와 같은 그래프를 Graph라고 하자 Graph에서 임의의 시작 노드를 잡아서 DFS(시작)를 한다. Graph가 서로 분리된 경우도 생각해야한다.(모든 정점에 대해서 DFS하기) DFS를 하면서 각 정점의 finis..