hihoCoder \ # 1121 2 분 도 1 · 2 분 도 판정
6787 단어 code
그림 옮 겨 다 니 기, 깊이 우선
그림 의 데이터 구 조 를 비교적 적 게 연습 해 왔 는데 이런 문 제 는 그래도 매우 좋다.
코드:
1 #include <iostream>
2 #include <vector>
3 #include <set>
4
5 using namespace std;
6
7 bool dye(vector<vector<int> > &graph, vector<int> &nodes, int i) {
8 for (auto j : graph[i]) {
9 if (nodes[j] == 0) {
10 nodes[j] = -1 * nodes[i];
11 if (!dye(graph, nodes, j))
12 return false;
13 }
14 else if (nodes[j] == nodes[i])
15 return false;
16 }
17
18 return true;
19 }
20
21 int main() {
22 int T, N, M;
23
24 cin >> T;
25 while (T--) {
26 cin >> N >> M;
27 vector<vector<int> > graph(N, vector<int>());
28 for (int i = 0; i < M; i++) {
29 int a, b;
30 cin >> a >> b;
31 graph[a - 1].push_back(b - 1);
32 graph[b - 1].push_back(a - 1);
33 }
34
35 vector<int> nodes(N, 0);
36 bool ok = true;
37 for (int i = 0; i < N; i++) {
38 if (nodes[i] == 0 && !graph[i].empty()) {
39 nodes[i] = 1;
40 if (!dye(graph, nodes, i)) {
41 ok = false;
42 break;
43 }
44 }
45 }
46 cout << (ok ? "Correct" : "Wrong") << endl;
47 }
48 return 0;
49 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
소스 코드가 포함된 Python 프로젝트텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
