http://acm.hdu.edu.cn/showproblem.php?pid=4751
建图，染色判断是否为二分图
#include<bits/stdc++.h> using namespace std; const int maxn = 105; const int maxm = 2e4+100; struct Edge{ int to, nx; }e[maxm]; int head[maxn], tot; int G[105][105]; int color[maxn]; void add(int from, int to){ e[++tot].to = to; e[tot].nx = head[from]; head[from] = tot; } bool dfs(int node, int c){ color[node] = c; for (int k = head[node]; k != -1; k = e[k].nx){ int to = e[k].to; if (color[to] != -1){ if (color[to] == c) return false; continue; } if (!dfs(to, c^1)) return false; } return true; } int main(){ std::ios::sync_with_stdio(false); int n; while(cin >> n){ memset(head, -1, sizeof(head)); memset(G, 0, sizeof(G)); memset(color, -1, sizeof(color)); tot = 0; for (int i = 1; i <= n; i++){ int k; while(cin >> k && k){ G[i][k] = 1; } } for (int i = 1; i <= n; i++){ for (int j = i+1; j <= n; j++){ if (!G[i][j] || !G[j][i]){ add(i, j); add(j, i); } } } bool ok = true; for (int i = 1; i <= n; i++){ if (color[i] == -1 && !dfs(i, 0)){ ok = false; break; } } cout << (ok ? "YES" : "NO") << endl; } return 0; }
