SCC
[BOJ / 2-SAT] 11281 2-SAT - 4
https://www.acmicpc.net/problem/11281 11281번: 2-SAT - 4 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 11281 2-SAT - 4 알고리즘 : 2-SAT / 강한연결요소(SCC) 이전 글에서 풀었던 2-SAT-3의 심화 문제입니다. 이전 문제는 가능한지 판별만 하였다면, 이번 문제는 가능한 케이스 한 개를 같이 출력하여야 합니다. (스페셜 저지) isVisited 변수는 SCC를 구성하는 순간 쓸모가 없어지므로 이 변수에 몇 번째 S..
[BOJ / 2-SAT] 11280 2-SAT - 3
https://www.acmicpc.net/problem/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 11280 2-SAT-3 알고리즘 : 2-SAT-3 / 강한연결요소(SCC) SCC 알고리즘를 활용한 알고리즘으로 2-SAT이라는 알고리즘이 있습니다. 전에 휴리스틱으로 풀었던 변수 3개까지 항을 가진 3-SAT은 NP문제인 반면 변수가 2개인 2-SAT은 강한연결요소를 이용하여 풀이할 수 있습니다. (X_i V X_j)인 경우 !X..
[BOJ / SCC] 4196 도미노
https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 4196 도미노 알고리즘 : 강한연결요소(SCC) SCC를 이용하여 사이클을 하나의 정점으로 만들어 위상정렬의 방식을 일부 따와서 푸는 문제입니다. 위상정렬은 사이클이 존재하면 풀리지 않으므로 SCC를 이용하여 사이클을 제거해주고 새로운 SCC에서 indegree가 0인 것을 카운팅 해주면 풀이됩니다. #include #include #include #include #include using na..