레야몬

1. 문제 한 심사위원은 반드시 찬성 또는 반대하는 두 사람을 고른다. 심사위원은 자신이 행사한 두 표 모두 반대되는 결과가 나오면 의심한다. 상근이가 포함된 다음 라운드 진출목록을 만들 수 있는지 없는지 구하시오. - 1 - 참가자의 수 n, 심사위원의 수 m \(2 \leq n < 1,000, 1 \leq m < 2,000)\) - m개의 줄 - 각 심사위원이 행사한 루트의, 정보 a, b \((1 \leq \left| a \right| , \left| b \right| \leq n, \left| a \right| \neq \left| b \right|)\) 정보가 x0인 경우 찬성표를 던질 것이다. 참가자의 번호는 1~n번이다. 상근이는 1번 참가자이다. 다음 라운드 진출 목록을 심사위원의 의심 없..

1. 문제 도현이는 경기장을 여러 구역으로 나누고, 어떤 선수가 A->B 움직임을 (A, B)로 표현한다. 다른 모든 구역에 도달할 수 있는 시작구역을 모두 찾자. - 1 - 테스트 케이스의 개수 \(T(1 \leq T \leq 11)\) - 1 - 구역의 수 N, 지시한 움직임의 수 M \(1 \leq N, M \leq 100,000)\) - M개의 줄 - 움직임 (A, B) \(0 \leq A, B < N)\) 가능한 모든 시작 구역을 오름차순으로 출력, 만일 그러한 시작 구역이 없으면 Confused 출력 2. 재정의 시작하면 모두 연결되는 정점 모두 출력 3. 해결 방법 SCC 알고리즘으로 구역 나누기 연결되는 그룹들을 모두 제거했을 때 남은 그룹의 개수가 1개면 그 그룹의 모든 원소. 0개면 모..

1. 문제 한 도미노 블록이 넘어지면 다음 도미노가 연쇄적으로 쓰러진다. 그러나 특정 다른 블록을 넘어뜨리지 못하게 배치되어 있다면 수동으로 넘어뜨려야 한다. 각 도미노 블록 배치가 주어질 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하라. - 1 - 테스트케이스의 개수 T - 1 - 정수 \(N, M(1 \leq N \leq 100,000)\) N: 도미노 개수, M: 관계의 개수 도미노 블록 번호는 1~N사이 정수다. - M개의 줄 - 두 정수 x, y(x번 블록이 넘어지면 y번 블록도 넘어짐) 손으로 넘어뜨리는 최소의 도미노 블록 개수 출력 2. 재정의 모든 노드를 다 지나기 위해 시작해야 되는 최소 노드 수 3. 해결 방법 SCC로 그룹 짓기 if(scc[i] ..

2-SAT - 3이랑 2-SAT - 4랑 한꺼번에 풀어서 함께 풀이해보려고 한다. 1. 문제 변수의 개수 N과 절의 개수 M, 그리고 식 f가 주어졌을 때, 식 f를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하라. (있으면 그 해를 출력하라 ) \(N(1 \leq N \leq 10,000)\), \(M(1 \leq M \leq, 100,000)\) N과 M 절 \((1 \leq, \left|i \right|, \left|i \right| \leq N)\) i, j가 양수인 경우 xi, xj를 음수인 경우는 ㄱx-i, ㄱx-j를 나타낸다. 2*a-1, !xa -> 2*a으로 하고 !a -> b와 !b -> a를 그래프에 추가하자 ex) Vertex[2*a].push_back(2*b-1) 그..

2-SAT - 3이랑 2-SAT - 4랑 한꺼번에 풀어서 함께 풀이해보려고 한다. 1. 문제 변수의 개수 N과 절의 개수 M, 그리고 식 f가 주어졌을 때, 식 f를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하라. (있으면 그 해를 출력하라 ) \(N(1 \leq N \leq 10,000)\), \(M(1 \leq M \leq, 100,000)\) N과 M 절 \((1 \leq, \left|i \right|, \left|i \right| \leq N)\) i, j가 양수인 경우 xi, xj를 음수인 경우는 ㄱx-i, ㄱx-j를 나타낸다. 2*a-1, !xa -> 2*a으로 하고 !a -> b와 !b -> a를 그래프에 추가하자 ex) Vertex[2*a].push_back(2*b-1) 그..

#include #include #include #include #define MAX_V 10001 using namespace std; int V, E; //정점의 개수 V, 간선의 개수 E int vs[MAX_V], scc[MAX_V]; //visited 방문했는가? 이미 scc에 들어갔는가? int cnt; //bfs로 탐색된 순서 stack st; vector res, gr; //result, graph bool cmp(vector x, vector y) //벡터 정렬 { return x[0] > V >> E; gr.resize(V+1); for(int i=0; i> a >> b; gr[a].push_back(b); } } int dfs(int..