hihoCoder#1121 二分图一•二分图判定

 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 }