scc
-
[백준] 4196번 도미노문제 풀이 2020. 9. 11. 18:21
4196 도미노 문제도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다.이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하자. 입력첫 번째 줄에 테스트 케이스의 개수가 주어진다.각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 도미노 블록의 번호는 1과 N 사이의 정수다..
-
[백준] 4013번 ATM문제 풀이 2020. 9. 5. 19:32
4013 ATM 문제) https://www.acmicpc.net/problem/4013 풀이)SCC, dp를 이용해서 푸는 어려웠던 문제였다. 같은 간선을 여러번 사용할 수 있기 때문에,임의의 정점을 방문한다고 할때 그 정점이 속한 SCC내의 모든 정점을 방문해서 최대 현금을 구한다. 과정1. kosaraju algorithm을 이용해 SCC을 구한다. SCC를 구할때, 각 정점이 어떤 SCC에 속하는지 표시해준다 //int node[i] => i 번 정점이 속하는 SCC번호 각 정점이 속하는 SCC의 총 현금을 저장해준다 //int scc[i] => i 번 SCC의 총 현금, 즉 SCC에 속한 정점들의 현금 합 SCC 끼리 연결될 수 있다면, 그 연결 간선을 저장해준다 //vector adj_scc[..
-
SCC-Kosaraju알고리즘 2020. 9. 3. 17:28
SCC(Strongly Connected Component) - 개념 : 방향그래프의 connected component 내 노드 u에서 v로 향하는 경로, 노드 v에서 u로 향하는 경로가 존재하면 해당 connected component를 SCC라 한다. (Connected component : 그래프는 여러개의 부분 그래프로 구성될 수 있는데 서로 연결되어 있는 여러개의 고립된 부분 그래프 각각을 connected component) - SCC를 찾는 알고리즘 Kosaraju's Algorithm : 2번의 DFS를 통해 SCC를 찾는다. 과정 1. digraph G에서 임의의 정점 i부터 dfs 수행 수행 속에서 먼저 끝나는 즉 다른 곳에 갈 곳이 없는 vertex를 stack에 push 하여 저장..