CodeForce 687A 二分图 交叉染色

题意

判断一个图是否是二分图，并分别输出两个集合的点。二分图是指一个图的点能分成两个集合，任意一个集合里的点都互不相连。更直观的定义大家请自行搜索。

分析

二分图的判断方法对图上的点进行交叉染色（即相邻的点染不同颜色），如果遇到两个相邻的点的颜色是一样的，说明不是二分图（可用三角形说明）。如果没有遇到过这样的点，说明是二分图。

PS

我的程序一直wa不知道错在哪里。网上的解法大多复杂。

解法

BFS，DFS均可

#include<cstdio> #include<vector> #include<cstring> using namespace std; #define N 100010 int color[N]; vector<int> g[N],ans[3]; bool flag = true; int n,m,t1,t2; void init() { memset(color,0,sizeof(color)); for(int i=0;i<m;i++) { scanf("%d %d",&t1,&t2); g[t1].push_back(t2); g[t2].push_back(t1); } } bool vis(int i){return color[i];} bool dfs(int now,int c) { color[now] = c;//染色 ans[c].push_back(now); for(int i = 0;i < g[now].size();i++) { int next = g[now][i]; if(vis(next)) { if(c == color[next]) return false; } else if(!dfs(next,3-c)) return false; } return true; } void printColor(int c) { int s = ans[c].size(); printf("%d\n",s); for(int i = 0; i < s;i++) printf("%d ",ans[c][i]); printf("\n"); } void print(bool ans) { if(ans == false) printf("-1\n"); else { printColor(1); printColor(2); } } int main() { scanf("%d%d",&n,&m); init(); for(int i=1;i<=n;i++) if(!vis(i) && !g[i].empty()) flag = dfs(i,1); print(flag); }