uva 10004 - Bicoloring

点击打开链接

题目意思：给定n个节点，还有l条边，每一个节点只有两种颜色可以上，但只能选择一种，并且要求相邻的节点之间不能有相同的颜色，判断给定的数据是否满足，如果满足

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 210;

int n , l , flag;
int node[MAXN][MAXN];//1-2，那么标记node[1][2] = 1；说明节点1到2有边
int color[MAXN];//存储每一个节点的颜色，两种取为0和1即可

//我们主要是要去判断是否有重复的点，那么如果这一行
void Bfs(){
    int i , j;
    for(i = 0 ; i < n ; i++){
        if(color[i] == -1)//如果这一点还没被上色，该行直接跳过，不影响后面判断
            continue;
        for(j = 0 ; j < n ; j++){
            if(node[i][j]){//如果i有到j的路径那么判断是否走过
                if(color[j] == -1)//没有被上色过
                    color[j] = !color[i];//直接上色
                else{
                    if(color[j] != !color[i]){//如果被上色过，那么只要当前要上的色和之前不同那么直接退出，说明存在周围颜色相同
                        flag = 0;//flag为0
                        return;
                    }
                }
            }      
        }    
    }
    flag = 1;//正常情况为1
}

void solve(){
    memset(color , -1 ,sizeof(color));//初始化为0
    color[0] = 1;//我们另第一个点为颜色1
    Bfs();
    if(flag)
       printf("BICOLORABLE.\n");
    if(flag == 0)
       printf("NOT BICOLORABLE.\n");   
}

int main(){
    int x , y;
    while(scanf("%d" ,&n) &&n){
        scanf("%d" , &l);
        memset(node , 0 , sizeof(node));
        for(int i = 0 ; i < l ; i++){
            scanf("%d%d" , &x , &y);
            node[x][y] = 1;
        }
        solve();
    }
    return 0;
}

方法2  dfs

//对节点上色属于无向图，那么我们搜索时候要用到无向的邻阶矩阵
//方法2 dfs
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int MAXN = 210;

int n , l , flag;
int map[MAXN][MAXN];
int vis[MAXN];//标记所上的颜色
//深搜
void dfs(int pos){
    for(int i = 0 ; i < n ; i++){
        if(map[pos][i]){//如果为1说明有边
            if(vis[i] == -1){
              vis[i] = !vis[pos];
              dfs(i);
            }
            if(vis[i] != -1){//已经被上过色
                if(vis[i] != !vis[pos]){
                    flag = 0;
                    return;
                }
            }
        }
    }
}

int main(){
    int x , y;
    while(scanf("%d" , &n) &&n){
        scanf("%d" , &l);
        flag = 1;//初始化为1
        memset(map , 0 , sizeof(map));
        memset(vis , -1 , sizeof(vis));
        for(int i= 0 ; i < l ; i++){
            scanf("%d%d" , &x , &y);
            map[x][y]++;//邻阶矩阵
            map[y][x]++;
         }
        vis[0] = 1;
        dfs(0);
        if(flag)
            printf("BICOLORABLE.\n");  
        else
            printf("NOT BICOLORABLE.\n");
    }
}

代码3： BFS

//对节点上色属于无向图，那么我们搜索时候要用到无向的邻阶矩阵
//方法3 BFS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int MAXN = 210;

int n , l , flag;
int map[MAXN][MAXN];
int vis[MAXN];
queue<int>q;

void Bfs(){
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(int i = 0 ; i < n ; i++){
            if(map[temp][i]){
                if(vis[i] == -1){
                    q.push(i);
                    vis[i] = !vis[temp];
                }
                if(vis[i] != -1){
                    if(vis[i] != !vis[temp]){
                        flag = 0;
                        return;
                    }
                }
            }
        }
    }
}

int main(){
    int x , y;
    while(scanf("%d" , &n) &&n){
        scanf("%d" , &l);
        flag = 1;
        memset(map , 0 , sizeof(map));
        memset(vis , -1 , sizeof(vis));
        for(int i= 0 ; i < l ; i++){
            scanf("%d%d" , &x , &y);
            map[x][y]++;//邻阶矩阵
            map[y][x]++;
         }
        vis[0] = 1;
        q.push(0);
        Bfs();
        if(flag)
            printf("BICOLORABLE.\n");  
        else
            printf("NOT BICOLORABLE.\n");
    }