首页 > 代码库 > hdu 5971 Wrestling Match 判断能否构成二分图

hdu 5971 Wrestling Match 判断能否构成二分图

2024-08-19 08:28:41   217人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=5971

Wrestling Match

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 25    Accepted Submission(s): 15


Problem Description
Nowadays, at least one wrestling match is held every year in our country. There are a lot of people in the game is "good player”, the rest is "bad player”. Now, Xiao Ming is referee of the wrestling match and he has a list of the matches in his hand. At the same time, he knows some people are good players,some are bad players. He believes that every game is a battle between the good and the bad player. Now he wants to know whether all the people can be divided into "good player" and "bad player".
 

 

Input
Input contains multiple sets of data.For each set of data,there are four numbers in the first line:N (1 ≤ N≤ 1000)、M(1 ≤M ≤ 10000)、X,Y(X+Y≤N ),in order to show the number of players(numbered 1toN ),the number of matches,the number of known "good players" and the number of known "bad players".In the next M lines,Each line has two numbersa, b(a≠b) ,said there is a game between a and b .The next line has X different numbers.Each number is known as a "good player" number.The last line contains Y different numbers.Each number represents a known "bad player" number.Data guarantees there will not be a player number is a good player and also a bad player.
 

 

Output
If all the people can be divided into "good players" and "bad players”, output "YES", otherwise output "NO".
 

 

Sample Input
5 4 0 0 1 3 1 4 3 5 4 5 5 4 1 0 1 3 1 4 3 5 4 5 2
 

 

Sample Output
NO YES
 

 

Source
2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学）
 

 

Recommend
wange2014   |   We have carefully selected several similar problems for you:  5981 5980 5979 5978 5977 
 

给定一个图，有可能是分散的图，其中有一些点是固定是颜色的，现在要求判断其能否成为二分图。

 

假如是分成了若干个联通快（块内的点个数 >= 2），对于每个联通快，如果有一些点是确定了的，那么就应该选那个点进行开始染色，途中如果遇到一些点已经确定颜色的了，但是和现在的想填的颜色不同，那么就应该输出NO，否则，进行染色即可。

对于点数为1的联通快，如果它没有被确定颜色的话，那么就直接输出NO了。

然后边数要开两倍，不然直接给wa，这里坑了我。一直做不出。

技术分享 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, m, x, y;
const int maxn = 1000 + 20;
struct node {
    int u, v, w;
    int tonext;
} e[2 * 10000 + 20];
int first[maxn];
bool vis[maxn];
int black = 1;
int white = 0;
int arr[maxn];
int ca[maxn];
bool in[maxn];
bool flag;
int num;
void add(int u, int v, int w) {
    ++num;
    e[num].u = u;
    e[num].v = v;
    e[num].w = w;
    e[num].tonext = first[u];
    first[u] = num;
}
void dfs(int cur, int col) {
    for (int i = first[cur]; i && flag; i = e[i].tonext) {
        int v = e[i].v;
        if (vis[v]) {
            if (arr[v] == col) {
                flag = false;
                return;
            }
        }
        if (vis[v]) continue;
        vis[v] = true;
        if (arr[v] == -1) {
            arr[v] = !col;
            dfs(v, !col);
        } else {
            if (arr[v] == col) {
                flag = false;
                return;
            } else {
                dfs(v, !col);
            }
        }
    }
}
void work() {
    num = 0;
    memset(arr, -1, sizeof arr);
    memset(ca, -1, sizeof ca);
    memset(in, 0, sizeof in);
    memset(first, 0, sizeof first);
    flag = true;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        add(u, v, 1);
        add(v, u, 1);
        in[v] = in[u] = 1;
    }
    for (int i = 1; i <= x; ++i) {
        int val;
        cin >> val;
        ca[val] = black;
        arr[val] = black;
    }
    for (int i = 1; i <= y; ++i) {
        int val;
        cin >> val;
        ca[val] = white;
        arr[val] = white;
    }
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 0 && ca[i] == -1) {
            cout << "NO" << endl;
            return;
        }
    }
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) continue;
        if (ca[i] == -1) continue;
        vis[i] = 1;
        arr[i] = ca[i];
        dfs(i, ca[i]);
    }
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) continue;
        arr[i] = black;
        dfs(i, black);
    }
    if (flag == false) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
}
int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    IOS;
    while (cin >> n >> m >> x >> y) {
        work();
    }
    return 0;
}
View Code

 

hdu 5971 Wrestling Match 判断能否构成二分图


联系
我们