Codeforces687A. NP-Hard Problem 染色判断二分图

题目链接：点击打开链接

新知识点，通过染色法判断二分图

从其中一个定点开始，将跟它邻接的点染成与其不同的颜色，最后如果邻接的点有相同颜色，则说明不是二分图，每次用bfs遍历即可。

AC code

/*2017年10月11日大几
AC
染色法判断二分图*/
#include <iostream>
#include <map>
#include <set>
#include <string>
#include<string.h>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
vector<int> G[maxn];
int col[maxn];
bool bfs(int s){
col[s]=1;
queue<int>q;
q.push(s);
while(!q.empty()){
int t=q.front();
q.pop();
int len=G[t].size();
for(int i=0;i<len;i++){
int v=G[t][i];
if(col[v]==-1){
col[v]=!col[t];
q.push(v);
}else if(col[v]==col[t]){
return false;
}
}
}
return true;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
memset(col,-1,sizeof(col));
for(int i=1;i<=n;i++){
G[i].clear();
}
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
bool flag=true;
for(int i=1;i<=n;i++){
if(col[i]==-1&&!bfs(i)){
flag=false;
break;
}
}
if(!flag) printf("-1n");
else{
vector<int> a,b;
for(int i=1;i<=n;i++){
if(col[i]==1){
a.push_back(i);
}else{
b.push_back(i);
}
}
printf("%dn",a.size());
for(auto it=a.begin();it!=a.end();it++){
if(it!=a.begin()) printf(" %d",*(it));
else printf("%d",*it);
}
printf("n");
printf("%dn",b.size());
for(auto it=b.begin();it!=b.end();it++){
if(it!=b.begin()) printf(" %d",*it);
else printf("%d",*it);
}
printf("n");
}
return 0;
}

最后

以上就是彪壮烤鸡为你收集整理的Codeforces687A. NP-Hard Problem 染色判断二分图的全部内容，希望文章能够帮你解决Codeforces687A. NP-Hard Problem 染色判断二分图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。