首页 > 代码库 > 二分图判定【图的搜索】
二分图判定【图的搜索】
二分图判定
给定一个图，要给图上每个顶点染色，并且要使得相邻的顶点颜色不同。问是否能最多用2种颜色进行染色？
参考如下：
Source Code:
#include <iostream>#include <vector>using namespace std;vector<int> Edge[1010];int colorArr[1010];void initColorArr(int length){ for(int i=0;i<=length;++i) colorArr[i]=0;}bool DFS(int index,int color){ colorArr[index]=color; for(int cnt=0;cnt<Edge[index].size();++cnt){ if(colorArr[Edge[index][cnt]]==color) return false; if(colorArr[Edge[index][cnt]]==0){ return DFS(Edge[index][cnt],-color); } } return true;}int main(){ int N,M; //n为顶点数,m为边数 int edge_a,edge_b; bool flag; while(cin>>N>>M){ for(int index=0;index<N;++index) Edge[index].clear(); initColorArr(N); for(int index=0;index<M;++index){ cin>>edge_a>>edge_b; Edge[edge_a].push_back(edge_b); Edge[edge_b].push_back(edge_a); } flag=true; for(int index=0;index<N;++index){ if(colorArr[index]==0){ if(DFS(index,1)==false){ cout<<"No"<<endl; flag=false; break; } } } if(flag) cout<<"Yes"<<endl; } return 0;}
二分图判定【图的搜索】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。