CF1680F Lenient Vertex Cover

题目传送门

DFS 树的性质。

首先注意到题面中的这一句话：

最多只能有一条边，满足两个顶点都在这个点集中。

显然，“最多只能有一条边”意思就是有 $0$ 条或 $1$ 条。

0 条

所以每条边都恰好只有一个顶点在点集中。

很自然想到二分图染色，每条边两个顶点颜色不同。

所以只要这个图是二分图，就一定有解。

1 条

有一条边的两个点同色，那么去掉这个边后，剩下的图一定就是一个二分图，就转化成了上一个情况。

先 DFS 一遍。一个显然的重要的性质是：对于原图中的每条边，要么是 DFS 树中的一条边，要么是一条返祖边（即一个点连向它祖先的边）。

因为二分图中没有奇环，所以这条去掉的边一定在所有奇环上，而不能在任何一个偶环上（这样去掉之后就全是偶环了）。

考虑去掉什么边。

返祖边

因为一个环在 DFS 树中一定是一条链加上一条返祖边，所以在 DFS 遇到返祖边时判断这个环是奇环还是偶环，就能统计出奇环数量了。如果奇环数量为 $1$，那么直接去掉那条返祖边即可。

树边

在统计环时把环上的所有树边都标记 $+1$，最后看是否有一个树边满足：

• 所在的奇环数 $=$ 奇环总数
• 所在的偶环数 $=0$

即可。

标记时用树上差分即可，不会的同学可以左转 OI Wiki。

最后判断答案时只需要再 DFS 一遍，按照深度奇偶性染色即可。

注意：有可能结果是：一条边满足两个顶点都不在点集中，其他每条边都有一个顶点在点集中。这时候只需要把所有颜色反转即可。

Code

int n, m, a[1000006], b[1000006];
vector<vector<int>>v;
int dep[1000006], fa[1000006], d1[1000006], d2[1000006], s1[1000006], s2[1000006];
int cnt;
int del1, del2;
void dfs(int k, int from) {
    rep(i, v[k].size()) {
        int x = v[k][i];
        if (x == from)continue;
        if (dep[x]) {
            if (dep[x] < dep[k]) {
                if ((dep[k] - dep[x]) % 2 == 0)d1[x]--, d1[k]++, del1 = x, del2 = k, cnt++;
                else d2[x]--, d2[k]++;
            }
            continue;
        }
        dep[x] = dep[k] + 1;
        fa[x] = k;
        dfs(x, k);
    }
}
pair<int, int> dfs2(int k) {
    pair<int, int>tmp, sum;
    sum.fi = d1[k], sum.se = d2[k];
    rep(i, v[k].size()) {
        int x = v[k][i];
        if (fa[x] != k)continue;
        tmp = dfs2(x);
        sum.fi += tmp.fi, sum.se += tmp.se;
    }
    if (sum.fi == cnt && sum.se == 0)del1 = fa[k], del2 = k;
    return sum;
}
int ans[1000006];
void getans(int k) {
    rep(i, v[k].size()) {
        if (ans[v[k][i]] != -1)continue;
        if (k == del1 && v[k][i] == del2)continue;
        if (k == del2 && v[k][i] == del1)continue;
        ans[v[k][i]] = 1 - ans[k];
        getans(v[k][i]);
    }
}
void solve() {
    cnt = 0;
    cin >> n >> m;
    v.resize(n);
    rep(i, n)v[i].clear();
    rep(i, m) {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
        v[a[i]].pb(b[i]);
        v[b[i]].pb(a[i]);
    }
    rep(i, n)ans[i] = -1, dep[i] = d1[i] = d2[i] = 0;
    dep[0] = 1;
    del1 = del2 = -1;
    dfs(0, -1);
    if (cnt > 1) {
        del1 = del2 = -1;
        dfs2(0);
        if (del1 == -1) {
            cout << "NO\n";
            return;
        }
    }
    ans[0] = 0;
    getans(0);
    rep(i, m)if (!ans[a[i]] && !ans[b[i]]) {
        rep(j, n)ans[j] = 1 - ans[j];
        break;
    }
    cout << "YES\n";
    rep(i, n)cout << ans[i];
    cout << '\n';
}