Educational Codeforces Round 128

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(无向图,图,奇数环,偶数环,树上差分)

题目

https://codeforces.com/contest/1680/problem/F

给一个连通无向图,n点,m 边

点覆盖: (所有边至少一个点属于点集

lenient点覆盖: 是点覆盖,且至多一条边两个点都在点集中

找出一个 lenient点覆盖

范围

t 1e4

n 1e6

5s

512MB

我的思路

首先 如果能黑白染色,成功,那么也就是每个边一端黑一端白, 全选黑或全选白都是一个答案

如果 黑白染色出现冲突,那么这两个点一定在一个奇环上

也就是这个奇环上存在两个点都是黑色, 最可以先把这个环上的边全部当作不存在,重新做染色,如果能成功, 计算这个环上同一个并查集点的颜色关系,

如果两两都不在同一个集合中那么说明拆了环都是独立的部分,那么任意染黑白即可

如果存在 a—–b 同集合中

a,b 同色 , [a..b]个数奇数的一半一定是黑白间隔

a,b 异色 , [a..b]个数偶数的一半一定是黑白间隔

换句话说, 其实原图去掉那个两个点都在集合中的边, 剩下的满足黑白染色,现在则是看哪些确定可以连起来

过程中检查冲突

如果剩余还有没连的 任选一个作为分割即可

但是 实现上能找环但如何找奇环

独立染色可以写,但合并时如何实现?

题解

前面几段和我想的一样, 奇偶黑白染色, 也就是需要在奇数环上剪断一条边,让整个染色合法

这里主要是 对无向图做dfs建立树

那么出现环的时候就是子节点指向父节点的时候

我们在dfs过程中黑白染色,那么出现回边时根据染色就可以知道它是奇环还是偶环,

如果我们统计了每条边出现在我们找到的奇环上的次数,和偶环上的次数,那么 如果一条边出现在奇数环上次数等于所有奇环次数,偶数环次数为零,那么删除这条边即可(可能有多个满足,任意删除一条)

// 必要性proof见下面, 充分显然

所以接下来就是当发生回环时,如何统计边在奇环偶环上出现次数了,如果直接对边计数,那么复杂度就过不了

树上差分, cnt[id]表示边id到根的所有边都 进行了+cnt[id],这样 当有点u到点v的回边时,就 cnt[faedge[u]]++,cnt[faedge[v]]–, 对于不在树上的回边edge[id] = {u,v}不需要差分直接统计, cnt[id]++

最后统计完后整理具体次数

然后找满足的边拆掉,再染色即可(注意拆掉边两端需要是黑色

性质证明

这里 显然的是 如果是两端同色的点, 那么它一定在所有奇环中,不在所有偶环中

也就是必要性显然

如果我们枚举了所有的环,那么拆掉它,所有奇数环也被拆掉了, 所以充分性也成立

问题是上面的实现 并没有枚举所有的环,枚举的只是树边+一条回边的所有环, 而环可能是由多条回边构成的

引理1: 如果环A和环B的一部分拼成环C,那么ABC中要么全是偶环,要么其中两个是奇环,

(这里拼成的意思是 A 和 B 有共用的一条链, C= (A-共用链)+(B-共用链)

那么要证明的是两部分, 这个两端同色的边也在未统计到的多回边的奇数环中,不在未统计到的多回边偶数环中

如果它(两端同色的边)不在未统计到的多回边奇数环中

那么这个环H(奇,回边=n) 可以拆成一个H1(奇,回边n-1) + H(偶,回边1)

因为H(偶,回边1) 我们一定计算到了, 只能递归下降, 且不会在 它们两的重复边上,因为它不在偶环上

那么这个环H(奇,回边=n) 可以拆成一个H1(偶,回边n-1) + H(奇,回边1)

因为H(奇,回边1) 我们一定计算到了 所以它在奇数环中

综上它一定在 未统计到的多回边奇数环中

如果它在未统计到的多回边偶数环中

那么这个环H(奇,回边=n) 可以拆成一个H1(偶,回边n-1) + H(偶,回边1)

它一定不在 H(偶,回边1) 中, 所以递归下降,且它也不在 两个环共用的边上

那么这个环H(偶,回边=n) 可以拆成一个H1(奇,回边n-1) + H(奇,回边1)

注意到上述结论, 这个边一定在这两个环里都有,因此这个边在它们重复的边上而不在偶环里

因此 得证

代码

https://codeforces.com/contest/1680/submission/158000410

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i = (a);i<(b);i++)
#define all(v) (v).begin(),(v).end()
const int N = 1000000;
int n,m;
int odd; // 奇环个数
int cnt0[N+10]; // cnt0[边]偶环个数，
int cnt1[N+10]; // cnt1[边]奇环个数，
int c[N+10]; //c节点颜色，
bool vis[N+10]; // dfs中访问过, 多次复用
int fe[N+10]; //fe父边
// 读入
pair<int,int> e[N+10]; // [边] = {点id,点id}
vector<pair<int,int>> G[N+10]; // [点] = 数组 {点id,边id}
//二分图染色同时找环
void dfs(int u,int p/*父边*/,int cl /*颜色*/ ) {
  c[u]=cl;
  vis[u]=1; // 管的当前到根的链上是否有, 减少重复计算 简化差分统计
  fe[u]=p;
  for(auto [v,id]:G[u]){
    if (id==p)continue;
    if (c[v]==-1){ // 未访问过
      dfs(v,id,cl^1);
    } else if(!vis[v]){ // 非父节点
      continue;
    } else if (c[v]==(cl^1)) { //偶环
      cnt0[id]++; // 不在树上的回边
      cnt0[p]++; // 树上边 差分统计 表示这个边到根的次数都+1
      if(~fe[v])cnt0[fe[v]]--; // 这个边到根的次数都-1
    } else { // if (c[v]==cl) {//奇环
      odd++; // 奇环个数
      cnt1[id]++;
      cnt1[p]++;
      if(~fe[v])cnt1[fe[v]]--;
    }
  }
  vis[u]=0;//回溯时撤销访问标记
}
// 整理差分数组，得到每条边的计数, 只用处理树边,递归, 不用处理非树的回边
void dfs2(int u) {
  vis[u]=1;
  for(auto [v,_]:G[u]){
    if (vis[v]) continue;
    dfs2(v);
    if (fe[u]!=-1&&fe[v]!=-1){
      cnt0[fe[u]]+=cnt0[fe[v]];
      cnt1[fe[u]]+=cnt1[fe[v]];
    }
  }
}
void dfs3(int u,int cl) { //二分图染色
  c[u]=cl;
  for(auto [v,_]:G[u]){
    if (c[v]!=-1) continue;
    dfs3(v,cl^1);
  }
}
void run(){
  // 一系列初始化
  odd=0;
  scanf("%d %d",&n,&m);
  rep(i,0,n) G[i].clear();
  fill(cnt0,cnt0+m+3,0);
  fill(cnt1,cnt1+m+3,0);
  fill(c,c+n+3,-1);
  fill(vis,vis+n+3,0);
  // 读入
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    e[i]={--u,--v};
    G[u].pb({v,i});
    G[v].pb({u,i});
  }
  dfs(0,-1,0); // 以0 为根染色0搜索
  // 整理树上差分数组 变成每个边的统计
  fill(vis,vis+n+3,0);
  dfs2(0);
  int id=-1;
  if (odd) {//存在奇环
    rep(i,0,m){
      // 需要完全相等 所有已知奇环都覆盖了它, 且没有偶环覆盖了它, proof? 必要性显然, 充分性呢?
      if (cnt1[i]==odd && cnt0[i]==0) {
        id = i; // 任选一条
        break;
      }
    }
    if (id == -1) {
      printf("NO\n");
      return;
    }
    //删边
    auto [u,v] = e[id];
    sort(all(G[v]));
    sort(all(G[u]));
    G[u].erase(lower_bound(all(G[u]),make_pair(v,-1)));
    G[v].erase(lower_bound(all(G[v]),make_pair(u,-1)));
  }
  // 再次染色
  fill(c,c+n+3,-1);
  dfs3(0,1);
  int f=(id==-1?0:c[e[id].first]^1); //保证被删边的端点颜色为1
  printf("YES\n");
  rep(i,0,n){
    printf("%d",c[i]^f);
  }
  printf("\n");
}
int main() {
  int T;
  scanf("%d",&T);
  while(T--)run();
  return 0;
}

// 1-2-3-4,3-1,4-1
// 奇边切 3-1在回边上
//
// 1-2-3-4-5, 3-1, 5-1
//
// 奇边切 1-2或2-3,在树边上
//

总结

知识点

无向图 = dfs -> 树+回边

而一部分无向图的环 = 多个树边+一条回边? 也可能由回边组成的环

树上差分 = 记录当前点到根的所有边的统一操作,如+1/-1

学了一手fill()函数,看起来很好用啊

然后 无向图 树上dfs, 的父边而不是父点 dfs(int u,int fe /*father edge*/)

参考

官方

csdn 修复了一些越界和等式操作, 修改了部分变量和包裹逻辑,整体