其实，如果仔细深究，就会发现：dfs本身也是分治！
看一下搜索树的产生过程：
随便选一个根，依次找把它剔除后产生的破碎的联通块，
再依次产生搜索子树。

对于这种匹配的题，往往有两个思路：二分匹配或分治
二分匹配就是把题目套上现成的匹配模型，
往往需要找到一种巧妙的染色方法以形成“二分”的图。
分治，则是通过这样的一种思想：
随便选一个节点或一条边，
把图断开，递归解决子图，然后通过这个点或边“调剂”一下，
许多图上找回路、找割定的问题都是用这个思想。

看一下这个题吧：
二分匹配似乎没戏了，那就分治。
断开一个点x，然后看分离出的子图。
对于每一个子图，需要大胆的不妨设只会有两种情况：
1.子图内部匹配成功。
2.子图内部无法匹配，富裕出一条连着x的某个邻居y的边(y,w)。

这个其实是需要证明的，不过，以下的算法就是证明：
对于情况1，把x与那个子图的所有连边统统划归x的“待匹配边表”
对于情况2，把(x,y)这个边“赠送”给那个子图，使得它可以匹配，
剩下的边归入“待匹配边表”
最后，把x的“待匹配边表”中的所有边两两匹配一下，
再看一下是否可以匹配或富裕一条边。

具体写的时候，可以用dfs巧妙地实现，dfs伪代码如下：
dfs u
   记录u的时间戳
   px=-1//记录用于“调剂”的那个边
   对于u的每一个邻居y
      如果y还没有访问，dfs y，
          如果返回多余一条边(y,w),则输出(u,y) (y,w)
          否则若px不是-1
              px=y
          否则输出(px,u) (u,y)并px=-1
      如果y访问过，但是它的时间戳比u晚，则
          若px不是-1
              px=y
          否则输出(px,u) (u,y)并px=-1
    最后返回px

• Re:雁过留声——分治与dfs (1012) hbl 2010-03-19 18:56:11