当前位置: 代码迷 >> 综合 >> 染色模板
  详细解决方案

染色模板

热度:50   发布时间:2024-01-14 22:27:14.0
#include <queue>  
#include <cstring>  
#include <iostream>  
using namespace std;  const int N = 999;  
int col[N], Map[N][N];  //0为白色,1为黑色   
bool BFS(int s, int n) 
{  queue<int> p;  p.push(s);  col[s] = 1;  //将搜索起始点涂成黑色while(!p.empty()) {  int from = p.front();  p.pop();  for(int i = 1; i <= n; i++) {  if(Map[from][i] && col[i] == -1) //如果从from到i的边存在(为邻接点) && i点未着色{  p.push(i);          //将i点加入队列col[i] = !col[from];//将i点染成不同的颜色   }  if(Map[from][i] && col[from] == col[i])//如果从from到i的边存在(为邻接点) && i点和from点这一对邻接点颜色相同,则不是二分图   return false;  }  }  return true;  //搜索完s点和所有点的关系,并将邻接点着色,且邻接点未发现相同色则返回true     
}  int main() 
{  int n, m, a, b;  memset(col, -1, sizeof(col));  cin >> n >> m;  //n 为有多少点,m为有多少边  for(int i = 0; i < m; i++) {  cin >> a >> b;  Map[a][b] = Map[b][a] = 1;   }  bool flag = false;  for(i = 1; i <= n; i++)  //遍历并搜索各个连通分支{    if(col[i] == -1 && !BFS(i, n)) //每次找没有着色的点进行判断,如果从它开始BFS发现相同色邻接点则不是二分图{   flag = true;  break;    }  }if(flag)  cout << "NO" <<endl;      else  cout << "YES" <<endl;  return 0;  
}  

 

 

  相关解决方案