题目意思:给定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"); }
时间: 2024-08-07 19:30:52