d[i]表示点i的度,c[i]是i的覆盖数

对于每条边(u,v),d[u]++,d[v]++

对于每个u,满足d[u]==1,则对他的邻接点v,c[v]++

如果存在i使得d[i]==0,无解
如果存在i使得c[i]>1,无解

• 传说图能否圈覆盖等价于判断拆点后二分图是否有完美匹配 (0) LiZhiXu 2008-12-07 18:03:43
  • 能否圈覆盖是说能否拆分成某几个圈的并么？ (23) wywcgs 2008-12-09 16:18:35
    • 不是这样的好像， 一个点只能在一个圈中。 (27) chaeyeon 2008-12-09 19:42:33
      • 我没看题。我说的并是所有圈中边的并等于边集，您说的是点集？ (0) wywcgs 2008-12-09 21:31:14
        • 嗯， 题目中说的是把点分开 (0) chaeyeon 2008-12-10 19:04:31
• 不知偶理解的对不对: (74) Jaakques 2008-12-07 18:11:48
  • 呵呵,我的方法是有问题,没考虑这样的情况,匹配ac了 (94) twilight 2008-12-07 22:19:23