题目
分析
这道题其实在问一个很简单的问题：我要在路口放路障，但是有个限制：一条路的两头不能都放路障（和题意矛盾）。
我们可以这样想：
-
想象你在给路口贴标签：
- 有些路口贴“要放路障”
- 有些路口贴“不放路障”
- 每个路口必须贴其中一种标签
-
规则很简单：
- 两个相连的路口不能都贴“要放路障”
- 但至少要有一个路口贴“要放路障”，不然这条路就没被封锁
这不就是在把路口分成两类吗？一类是“路障”，一类是“没路障”。但相连的路口必须属于不同类。
这就是二分图的本质：我们在把点分成两类，相连的点不能在同一类里。而解二分图，可以用染色法：帮我们区分这两类点。
如果发现有些点怎么都无法合理分类（比如某个环的长度是奇数），那就说明这个封锁方案是不可能的。
bool dfs(int u, int c, int& count1, int& count2)
{
color = c;
if (c == 1)
count1++;
else
count2++;
for (int v : graph)
{
if (color[v] == 0)
{
// 相邻节点染成相反的颜色
if (!dfs(v, 3 - c, count1, count2)) //3-1=2， 3-2=1。切换颜色
return false;
}
else if (color[v] == c)
{
// 如果相邻节点颜色相同，则不是二分图
return false;
}
}
return true;
}考虑到可能存在多个通路，还要对每个（没有染色的）节点重复上述过程。累加用色最少的那个颜色的数量，就是答案。
答案
思考
为什么二分图染色可以解决这个问题？可以类比之前的“（自己的）敌人”和“（自己的）敌人的敌人”这样的关系。相邻节点肯定是“敌人”：无论如何，它们不能都放路障。而“敌人的敌人”必须和自己一样也放路障。但如果出现矛盾：一个敌人的敌人因为某种原因成了自己的敌人，那么肯定不对了。
因此，染色实际上是在将节点分成两个独立集，而路障必须放在其中一个集合中。
二分图染色有很多实际应用：
- 课程安排问题
- 社交网络分析
- 资源分配优化