CodeForces 687A--判断二分图

题意：判断一个无向图是否是一个二分图，如果是输出二分图的左右子集，如果不是，则输出-1.

分析：

判断二分图的关键：两个子集是否独立，即相邻两个顶点不在同一个子集，若是就是二分图，若不是，则不是二分图。因此经常用二

分图染色法来判断一个无向图是否是二分图。为染色的顶点标记-1，然后对顶点进行染色（0），在对该顶点相邻的顶点然不同的颜色（1），dfs遍历各顶点，dfs(g[k][i],c^1),c^1:异或，0^1=1，1^1=0;如果最后一个顶点有两个不同的颜色，也就是说这个顶点和他的相

邻顶点同色，则说明不是二分图。下面上代码：

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
vector<int> g[maxn],v[2];
bool ok;
int color[maxn];
///二分图染色法
void dfs(int k,int c) ///顶点k，染色c
{
if (color[k] != -1) ///顶点k已染色
{
if (color[k] != c) ///染得色不同，即同子集间的两个顶点有边
ok=true;
return;
}
color[k] = c; ///顶点k染色
v[c].push_back(k);
int len = g[k].size(); ///边数
for (int i = 0; i < len; ++i)
dfs(g[k][i],c^1); /// 0 -> 1,, 1 -> 0;相邻顶点然不同的颜色，位异或，0^1=1，1^1=0
}
void print(vector <int> & t)
{
int len = t.size();
printf("%dn",len);
for (int i = 0; i < len; ++i)
i ? printf(" "):printf("%d",t[i]);
printf("n");
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0; i < m; ++i)
{
int u,w;
scanf("%d%d",&u,&w);
g[u].push_back(w);
g[w].push_back(u);
}
ok=false;
memset(color,-1,sizeof color);
for (int i = 1; i <= n; ++i)
{
if (color[i] == -1) ///未染色
dfs(i,0); ///染0色
}
if (ok) ///不是二分图
printf("-1n");
else
{
print(v[1]);
print(v[0]); ///输出左右子集
}
return 0;
}

最后

以上就是友好高跟鞋最近收集整理的关于CodeForces 687A--判断二分图的全部内容，更多相关CodeForces内容请搜索靠谱客的其他文章。