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 }

좋은 웹페이지 즐겨찾기