oVeron

해당 그래프를 위상 정렬하여 진입 차수가 0인 모든 정점에 바이러스를 풀면 될 것이다.그런데 이 그래프는 사이클이 존재할 수 있으므로, SCC를 이용해 사이클을 묶어 줘야 한다.SCC를 만들고 위상 정렬해 진입 차수가 0인 정점의 개수를 찾으면 된다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXN = 100000;int N, M;vector graphf[MAXN], graphr[MAXN];bool vis[MAXN];stack st;vector> SCC;int SCCnum[MAXN]; //정점 i의 SCC 번호vector graphSCC[MAXN..

알고리즘/baekjoon 2024. 9. 1. 11:15

https://www.acmicpc.net/problem/16367 16367번: TV Show Game Your program is to read from standard input. The input starts with a line containing two integers, k and n (3 < k ≤ 5,000, 1 ≤ n ≤ 10,000), where k is the number of lamps and n the number of game participants. Each of the following n lines contains t www.acmicpc.net (x1 V x2 V x3) = (x1 V x2) Λ (x2 V x3) Λ (x3 V x1) R, B를 각각 음수, 양수로 처리하고..

알고리즘/baekjoon 2023. 3. 6. 09:39

https://www.acmicpc.net/problem/3648 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 2-SAT + (x1 V x1) 이 명제를 추가하면 x1은 무조건 참이 되기에, 상근이는 진출할 수 있다. #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int N, M; v..

알고리즘/baekjoon 2023. 3. 6. 09:18

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 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)로 이루어져 있으며..

알고리즘/baekjoon 2023. 3. 5. 23:27

https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 1. 그래프를 SCC로 묶어 새로운 SCC 그래프를 만든다. 3977번 축구 전술 문제와 거의 같은 형태이다. 2. SCC 그래프에서 트리 dp를 이용해 최댓값을 얻는다. dp[i] : 임의의 레스토랑 정점에서 정점 i까지 도달하는데 ATM에서 인출할 수 있는 돈의 합의 최댓값 이때 현재 정점 i에서 레스토랑 정점까지 갈 수 있느냐 여부가 중요하기 때문에, 갈 수 있으면 현재 정점의..

알고리즘/baekjoon 2023. 3. 4. 10:57

https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 1. SCC를 이용해 그래프를 비순환 방향 그래프(DAG)로 바꾼다. 2. 진입 차수가 0인 정점을 찾는다. 이러한 정점이 하나면 그 SCC를 출력하고, 둘 이상이면 Confused를 출력한다. 같은 SCC로 묶인 정점들의 DFS_min 값은 다를 수 있다. 때문에 인접한 두 정점의 DFS_min 값이 다를 때 진입차수를 하나 더하는 방식으로 진행한다면 무조건 틀린다. #inclu..

알고리즘/baekjoon 2023. 3. 3. 17:09

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 1. 가장 먼저 떠오르는 방법은 DFS를 이용해 분리된 그래프의 개수를 구하는 것이다. 하지만 각 그래프의 root를 모르기 때문에 실행하기 어려운 방법이다. 2. 각 그래프의 root를 구해야 한다는 점에서 위상 정렬을 떠올려 볼 수 있다. 사이클이 존재할 수 있으므로 SCC와 결합시켜 생각한다면 풀 수 있을 것이다. 다만 실제로 위상 정렬의 방식을 SCC와 결합해 구현하기는 힘들어서, SCC 타잔 알고리즘의 ..

알고리즘/baekjoon 2023. 3. 1. 11:13

https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int V, E; vec..

알고리즘/baekjoon 2023. 3. 1. 09:05