图论-二分图判定
引子：
现在有一群学生，这些学生之间有敌对关系。而现在又有一些信息表示这些同学之间的关系，信息的格式为：X-Y，表示X与Y之间存在敌对关系。请问是否可以把些学生分成两个阵营使同一个阵营之间不存在敌对关系？
分析：
有同学会注意到这一个引子的某些叙述与我在并查集中的叙述一致。以至于有部分同学认为这道题可以用并查集完成。但细心观察我们会发现，并查集是为了判断两点是否在同一集合，而我们在这个问题中并不需要判断两点是否在同一集合，即并查集解该题无效。我们的目的是快速解出该问题，所以需要抛开这个有争议的思路。所以，我们有必要引入一个新的概念：二分图。
解释：
下面我们解释二分图的概念。二份图指一个无向图的点可以被分为两个集合，且任意一个集合中的任意两个点不能直接可达，或者说任意一条边的两个顶点分属于两个不同的集合,这样的图被称为二分图。
思路：
于是乎我们现在有了问题的思路。 “请问是否可以把些学生分成两个阵营使同一个阵营之间不存在敌对关系？” 一句中暗含二分图的基本概念,所以我们可以通过二分图来解决该问题。而题目的问题是是否可以，即我们所求的是这一个图是否为二分图，也就是二分图的判定。我们只需要判定这一个图是否为二分图就可以完成该问题。
解决：
1.方法：
根据二分图任意一条边的两个顶点分属于两个不同的集合，我们可以采取标记的方式，将任意一条边的两个顶点标记成两个不同的数字，如果所有边的两个顶点的数字都不同，这个图就是二分图；反之则不是。（这个方法被称为 染色法 ）
2.初始化及建图：
初始化：
针对这个问题，我们需要一个数组标记每个顶点所属集合的情况，即染色的情况。
这里我们用数组book[]来标记，这个标记数组的含义为：
1. book[i]表示第i个顶点，或者说编号为i的顶点的情况。
2. book[i]==0 表示第i个顶点没有被染色。
3. book[i]==1 表示第i个顶点被染色成第一种颜色。
4. book[i]==2 表示第i个顶点被染色成第二种颜色。
于是有数组定义：
int book[N];//book[]:染色情况
建图：
还记得我们在并查集补充中讲过的存储图吗？事实上图的存储（邻接矩阵/邻接表/直接存储）一般情况下邻接表最优（这里我们不讨论链式前向星），即用vector存图。
不知道vector不要紧，我们在这里复习一下——
邻接表存图：
首先我们要弄清楚什么是vector。
你可以把vector理解为动态数组，也就是可自动申请空间的数组。这与邻接矩阵的本质区别在于：
1. vector不用存储多余的信息（如没有边，在邻接矩阵中体现为边权为无穷大，自己到自己等），节省了许多空间。
2. vector的遍历只需将每一条边遍历到，而邻接矩阵则需要将不存在的边遍历，即时间复杂度为O(n2)，其中n为顶点个数。
而且这个问题有没有特殊需要存在，所以用vector最优具有绝对优势。
“我们都知道，每一条边都有两个顶点，有时还会有其对应的权值，所以我们用
x y val来存储这些信息。
但本问题讨论的是二分图的判定，无需关心权值的问题，即无权。”
——引用自《数据结构之并查集补充》
根据上面的论述，我们可以知道vector应当用整数类型（vector <int>）。
需要清楚的是，单个vector <int>存放的是每一个点的邻接点，所以我们用
vector <int> edge[N]
来存放每一个顶点的邻接点信息。
所以我们可以这样存图：
const int N=1000+1;//边的上限
vector <int> edge[N];//vector存图（动态数组的数组）
使用vector的数据读入：
for(int i=1;i<=m;i++)//读入m组信息，m:信息数
{
int a,b;//临时存储变量
scanf("%d%d",&a,&b);//读入
edge[a].push_back(b);//存双向边，将a,b分别设为b与a的邻接点
edge[b].push_back(a);
}
至此，我们所有的准备工作结束了。
3.dfs(深度优先搜索)遍历
之前我们说过，我们需要将这一个图染色后才能确定它是否是一个二分图。
所以我们有必要进行遍历，这里我们采用dfs的方式遍历（bfs用得少）。
1. dfs()函数的定义：首先我们需要确定这个深搜函数的作用及参数。它的作用很明确，就是从一个点出发，遍历并染色这个图（而且判断从这个点出发形成的图是否为二分图）。所以我们得知，这个深搜函数需要且仅需要一个参数x表示出发点的个数。
2. dfs()函数的遍历：现在已知一个顶点，怎样遍历这个点的邻接点？其实只需要提取edge[x]的信息就行了。所以我们应这样遍历：
for(int i=0;i<edge[x].size();i++)//遍历x的邻接点
{
int u=edge[x][i];//提取x的第i个邻接点
}
//注意最好不要写成i<=edge[x].size()-1，以免报错。
dfs()函数的整体框架：对于这个问题中的深搜函数我们需要bool或int类型的返回值（原因是我们需要知道是否可以形成二分图）,这里我更倾向于用bool。所以整体代码框架如下：
bool dfs(int x)//x:出发点的编号，返回值为bool
{
for(int i=0;i<edge[x].size();i++)
{
int u=edge[x][i];
}
}
4.染色的过程：
在次我们需要对函数进行升级，将其变成双参函数。
原因其实很简单，是因为我们要确定颜色的编号，所以用参数c作为需要染色成的颜色编号。所以深搜函数的所用变成了将当前点染色并遍历，最后判断从这个点出发的图是不是二分图。
所以给该点染色的代码是：
book[x]=c;//将x点染成c号颜色
我们说，要给一点的邻接点染上相反的颜色，一条边的两个顶点同色就代表这个图不是二分图，这里我们可以在遍历的过程中完成染色及判断：
if(book[u]==0) //如果邻接点没有被染色
{
if(!dfs(u,3-c)) return false;//给u染上相反的颜色并判断以u出发的图是否为二分图，不是就返回false
if(book[u]==c) return false;//(u已经上色完成)u与x同色就说明这个图不是二分图，返回false
}
在程序最后，遍历完了却仍然没有返回false，就说明该图是二分图，返回true。
所以深搜函数的完整代码是：
bool dfs(int x，int c)//x:出发点的编号，返回值为bool,c:颜色编号
{
book[x]=c;//将x点染成c号颜色
for(int i=0;i<edge[x].size();i++)//遍历x的邻接点
{
int u=edge[x][i];//提取x的第i个邻接点
if(book[u]==0) //如果邻接点没有被染色
{
if(!dfs(u,3-c)) return false;//给u染上相反的颜色并判断以u出发的图是否为二分图，不是就返回false
}
if(book[u]==c) return false;//(u已经上色完成)u与x同色就说明这个图不是二分图，返回false
}
//注意最好不要写成i<=edge[x].size()-1，以免报错。
return true;
}
5.最终判断：
可现在有一个问题：这一个需要判断的图有没有可能是有多个图组成的？
答案是肯定的。
为了解决这种情况，我们需要循环对没有被染色的顶点染色，这里我建议把这个过程封装为一个函数。
与 “4.染色的过程” 类似，如果
dfs(x)==false;//x:当前出发点
那么这个图就不是二分图；
繁殖，所有点都被染色完毕，还没有返回false，那么这个图就是二分图。
我们命名这个判断函数为check()，其中函数返回值为bool，且没有参数。
这个函数的代码如下：
bool check()//声明判断函数，返回值为bool
{
for(int i=1;i<=n;i++)//遍历查找没被染色的点进行染色
{
if(book[i]==0)//如果没被染色
{
if(dfs(i,1)==0) return false;//染色失败则返回false，表示这不是个二分图
}
}
return true;//遍历完了都没有返回，说明这是个二分图，返回true
}
所以最终我们这样判断该图是否为二分图：
1. check()==false：该图不是二分图。
2. check()==true：该图是二分图。
附加.阵营输出：
最后一个问题：如果该图是一个二分图，那么怎样正确输出两个阵营所包含的点呢？
你一定记得我们在文章开始就曾讨论的二分图的概念与染色法的思路。
我们对染色法的讲解有一句话极为重要：
“将任意一条边的两个顶点标记成两个不同的数字”
同样的，二分图的概念中也有这样的一句话：
“任意一条边的两个顶点分属于两个不同的集合”
我们将这两句结合起来看，会发现，染色后的二分图中不同颜色的两个顶点分别属于两个不同的集合（阵营），所以颜色1属于阵营1；颜色2属于阵营2。
综上，我们只需要遍历查找点的颜色，代码如下:
void output()//输出函数的声明
{
if(check()==false) printf("不是。");//如果该图不是二分图，输出不是。
else //否则
{
for(int i=1;i<=n;i++)//输出集合一的顶点编号
{
if(book[i]==1) printf("%d ",i);
}
printf("\n");
for(int i=1;i<=n;i++)//输出集合二的顶点编号
{
if(book[i]==2) printf("%d ",i);
}
}
return ;//象征性返回
}
至此我们的问题就得到了解决，你可以将已写好的程序输入以下样例检测程序：
输入:
6 4
1 2
3 4
3 6
4 5
输出:
1 3 5
2 4 6
现在献上完整代码：
#include <bits/stdc++.h>
using namespace std;
int n,m;//n:顶点个数，m:敌对关系条数
const int N=1000+1;//边的上限
vector <int> edge[N];//vector存图（动态数组的数组）
int book[N];//book[]:染色情况
bool dfs(int x,int c)//x:出发点的编号，返回值为bool，c:颜色编号
{
book[x]=c;//将x点染成c号颜色
for(int i=0;i<edge[x].size();i++)//遍历x的邻接点
{
int u=edge[x][i];//提取x的第i个邻接点
if(book[u]==0) //如果邻接点没有被染色
{
if(!dfs(u,3-c)) return false;//给u染上相反的颜色并判断以u出发的图是否为二分图，不是就返回false
}
if(book[u]==c) return false;//(u已经上色完成)u与x同色就说明这个图不是二分图，返回false
}
//注意最好不要写成i<=edge[x].size()-1，以免报错。
return true;
}
bool check()//声明判断函数，返回值为bool
{
for(int i=1;i<=n;i++)//遍历查找没被染色的点进行染色
{
if(book[i]==0)//如果没被染色
{
if(dfs(i,1)==0) return false;//染色失败则返回false，表示这不是个二分图
}
}
return true;//遍历完了都没有返回，说明这是个二分图，返回true
}
void output()//输出函数的声明
{
if(check()==false) printf("不是。");//如果该图不是二分图，输出不是。
else //否则
{
for(int i=1;i<=n;i++)//输出集合一的顶点编号
{
if(book[i]==1) printf("%d ",i);
}
printf("\n");
for(int i=1;i<=n;i++)//输出集合二的顶点编号
{
if(book[i]==2) printf("%d ",i);
}
}
return ;//象征性返回
}
int main()
{
cin>>n>>m;//读入
for(int i=1;i<=m;i++)//读入m组信息，m:信息数
{
int a,b;//临时存储变量
scanf("%d%d",&a,&b);//读入
edge[a].push_back(b);//存双向边，将a,b分别设为b与a的邻接点
edge[b].push_back(a);
}
output();//调用输出函数
return 0;
}
（注：本文章来自作者洛谷博客）
