Menu
Article ACM

CodeForces 19E Fairy

NodeKey

NodeKey

• 3 min read

一道二分图性质的应用 + 树形DP ？

看博客里都说是树形DP，但我觉得应该是树上前缀和更加合适一些

题意：
给你一个图，让你删除一条边，使得剩下的图是二分图。
输出可删边数并顺序输出边的序号。

思路：
首先你必须知道判定二分图的充要条件 —— 不存在奇环。
如果只是让你判定二分图的话，倒是随便搜一遍就可以解决的问题。
但是这里必须让你删掉一条边……

写不来……感觉不好写，最后无奈去看题解了……

先整理一下判断思路：

  1. 如果不存在奇环，那么原图本来就是一张二分图，每一条边都满足条件
  2. 覆盖了所有的奇环，并且不能覆盖偶环的所有边

为什么同时不能覆盖偶环，这个我还真没想到，但是在纸上画一画就是很显然的了，同时覆盖奇环和偶环的边删去后，两个环会变成一个新的环，偶数+奇数 还是奇数。所以不能覆盖偶环。

因此得出如下具体实现，随便生成一棵生成树，用树上前缀和计算出每一条树边覆盖的奇环数和偶环数。
如果奇环数量大于 1 ，那么非树边必定不可能是满足条件的，因为非树边最多只能覆盖一个环，两个及以上就是重边了。因此非树边只有在奇环数量等于 1 的时候才需要我们去考虑，如果该非树边覆盖了奇环，则删之。
而对于树边，判断其覆盖奇环数和偶环树是否满足条件即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;
int n, m, top, cnt;

pii edges[maxm];
int head[maxn];
int idx;

int odd[maxn], even[maxn];
int dep[maxn], edge_type[maxm];
bool vis[maxn];

void addEdge(int u, int v)
{
    edges[idx] = make_pair(v, head[u]);
    head[u] = idx++;
    edges[idx] = make_pair(u, head[v]);
    head[v] = idx++;
}

void dfs(int u, int e)
{
    vis[u] = true;
    dep[u] = ++top;
    int v;
    for (int id = head[u]; ~id; id = edges[id].second) {
        if (edge_type[id] == -1)
            continue;
        v = edges[id].first;
        if (!vis[v]) {
            edge_type[id] = edge_type[id ^ 1] = -1;
            dfs(v, id >> 1);
            odd[e] += odd[id >> 1];
            even[e] += even[id >> 1];
        } else {
            if (edge_type[id] == 1)
                odd[e]--;
            else if (edge_type[id] == 2)
                even[e]--;
            else {
                if ((dep[u] - dep[v]) & 1)
                    even[e]++, edge_type[id] = edge_type[id ^ 1] = 2;
                else
                    odd[e]++, edge_type[id] = edge_type[id ^ 1] = 1, cnt++;
            }
        }
    }
    top--;
}

int ans[maxn], anum;

int main()
{
    int u, v;
    scanf("%d %d", &n, &m);
    fill(head, head + n + 1, -1);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    if (cnt == 0) {
        printf("%d\n", m);
        for (int i = 1; i <= m; i++)
            printf("%d ", i);
    } else {
        for (int i = 0; i < m; i++)
            if (odd[i] == cnt && even[i] == 0)
                ans[anum++] = i;
            else if (cnt == 1 && edge_type[i << 1] == 1)
                ans[anum++] = i;
        printf("%d\n", anum);
        for (int i = 0; i < anum; i++)
            printf("%d ", ans[i] + 1);
    }
    return 0;
}
Share