1. 풀이 이분그래프를 확인하는 방법은 다음과 같다. (1) 2개의 색깔을 가지고 dfs를 통해 인접한 노드에 다른 색깔을 칠하며 전체를 다 칠하기. (2) 2중 포문을 통해 인접한 노드에 다른색이 칠해져 있는지 확인. -> 다른색이 칠해져 있으면 이분그래프 될 수 없음. (3) 이분그래프 2. 소스코드 import sys sys.setrecursionlimit(10 ** 7) k = int(input()) turn = [1, 0] def cheak(): for v in range(1, V + 1): nowColor = colorV[v] for conNode in graph[v]: if colorV[conNode] == nowColor: print("NO") return print("YES") def d..

1. 최단거리 2. 최소스패닝 트리(MST)

파티에 진실을 아는사람이 있으면 진실만을 말해야 한다. 새롭게 진실을 알게 된 사람을 고려해야한다(그사람이 참석하는 다른 파티에서도 진실을 말해야한다) ​ 1. 풀이 (1) 그래프 연결 1) 파티를 하나의 노드로 본다. 2) 파티를 두개씩 짝지어서 비교하면서, 한사람 이상을 공유하면 연결한다. (파티1과 파티2를 비교하여 둘다 참여하는사람이 있으면 연결한다.) 3) 연결이 완료되면 탐색을 시작한다. (2) 탐색 1) 연결된 노드(파티)들을 탐색한다 2) 연결된 파티들 중 하나의 파티에서라도 진실을 아는사람이 있다면, 연결된 모든 파티에는 진실을 말해야한다 3) 한명도 진실을 아는사람이 없다면 연결된 모든 파티에는 과장을 해도된다. ​ 2. 소스코드 from collections import deque N..

1. 풀이 (1) 입력이 하나의 그래프임이 보장될때 트리일 조건은 (노드개수-1)==(간선개수)가 된다. (2) 간선개수가 0인것은 빈트리이므로 이것역시 트리이다. 2. 소스코드 #include #include #include #include using namespace std; int main() { int num1, num2; string ans; int t = 1; while (1) { cin >> num1 >> num2; if (num1 < 0) { break; } // test case else { vector graph; set s; // 입력 while (1) { if (num1 == 0 and num2 == 0) { break; } else { graph.push_back(make_pair..