HDU - 4751 Divide Groups 二分图判定
程序员文章站
2022-05-22 13:58:31
...
其实就是分成两个集合,判断是否合法
对于本题:有的人和两个集合的人都认识 所以放到哪个里面都行,,所以 判断不合法的依据是: 放到了一个集合中,但是 存在有两个人认不认识的情况
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 100 + 7;
int un[maxn][maxn], vis[maxn];
int n, x;
void init() {
memset(vis, -1, sizeof vis);
memset(un, 0, sizeof un);
for(int i = 1; i <= n; ++i) {
int x;
while(scanf("%d", &x) && x) {
un[i][x] = 1;
}
}
}
bool bfs(int t) {
int i, j, w;
queue<int> q;
q.push(t);
while(!q.empty()) {
w = q.front();
q.pop();
for(int i = 1; i <= n; ++i) {
if(w == i || (un[i][w] && un[w][i])) continue;
if(vis[i] == -1) {
vis[i] = vis[w]^1;
q.push(i);
}
else if(vis[i] == vis[w])
return true;
}
}
return false;
}
void solve() {
for(int i = 1; i <= n; ++i) {
if(vis[i] == -1) {
vis[i] = 0;
if(bfs(i)) {
cout << "NO" << endl;
return;
}
}
}
cout << "YES" << endl;
}
int main() {
while(scanf("%d", &n)!=EOF && n) {
init();
solve();
}
return 0;
}
推荐阅读