题目链接https://ac.nowcoder.com/acm/problem/124640
解题思路：深搜 + 二分图染色问题
1 #include <bits/stdc++.h> 2 using namespace std; 3 vector<int> mp[1010]; //mp[i]存储i这个选手的所有出边 4 int n; //总选手数 5 int color[1010]; //存储每个选手是good还是bad 6 bool dfs(int p, int c) { //深搜，假设p选手是c的话，看是否有矛盾出现 7 //有矛盾返回false,无矛盾返回true 8 color[p] = c; 9 for (int i = 0 ; i < mp[p].size(); i++) { //遍历p的所有出边 10 if (color[mp[p][i]] == c) { 11 return false; 12 } 13 if (color[mp[p][i]] == 0 && !dfs(mp[p][i], -c)) { //如果该点还没被染色，就把它染为另外一种颜色 14 return false; 15 } 16 } 17 return true; 18 } 19 void solve() { 20 for (int i = 1; i <= n; i++) { 21 if (color[i] == 1) { //如果该选手是good的话 22 if (!dfs(i, 1)) { 23 cout << "NO" << endl; 24 return; 25 } 26 } 27 } 28 for (int i = 1; i <= n; i++) { 29 if (color[i] == -1) { //如果该选手是bad的话 30 if (!dfs(i, -1)) { 31 cout << "NO" << endl; 32 return; 33 } 34 } 35 } 36 for (int i = 1; i <= n; i++) { 37 if (color[i] == 0) { 38 if (!dfs(i, 1)) { 39 cout << "NO" << endl; 40 return; 41 } 42 } 43 } 44 for (int i = 1; i <= n; i++) { 45 if (color[i] == -5) { 46 cout << "NO" << endl; 47 return; 48 } 49 } 50 cout << "YES" << endl; 51 } 52 int main() { 53 int m, x, y; //总边数，good选手数，bad选手数 54 while (cin >> n >> m >> x >> y) { 55 for (int i = 1; i <= n; i++) { //每一次都要把i这个选手的所有出边清空并赋初值-5 56 mp[i].clear(); 57 color[i] = -5; //-5表示i选手的是good还是bad是未知的 58 } 59 for (int i = 0; i < m; i++) { //遍历m场比赛 60 int a, b; 61 cin >> a >> b; //a选手和b选手之间有场比赛 62 color[a] = 0; //0表明该选手有比赛，需要被染色 63 color[b] = 0; //0表明该选手有比赛，需要被染色 64 mp[a].push_back(b); //a连向b有一条边 65 mp[b].push_back(a); //b连向a有一条边 66 } 67 for (int i = 0; i < x; i++) { //x个已知的good选手 68 int t; 69 cin >> t; 70 color[t] = 1; //1表示该选手是good选手 71 } 72 for (int i = 0; i < y; ++i) { //y个已知的bad选手 73 int t; 74 cin >> t; 75 color[t] = -1; //-1表示该选手是bad 76 } 77 solve(); //解决问题 78 } 79 return 0; 80 }