欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}