Atcoder CODE FESTIVAL 2017 qual B C - 3 Steps 二分图题目链接题意我的思路结论证明具体写法Code

题目链接

题意

给定一个无向图，(n)个点，(m)条边（(n,mleq 1e5)）.

重复如下操作：

选择相异的两点u,v满足从点u出发走三条边恰好能到达点v。在这样的u,v点对之间添一条边（如果已经存在则无需再次添加）。

问最多能添加多少条边。

我的思路

（是写给自己看的读者老爷可以跳过去的部分）

首先， 所有距离为奇数的点对之间都能添边。因为

3-1+3=5
5-1+3=7
5-1+5=9
7-1+3=9
7-1+5=11
7-1+7=13
9-1+3=11
9-1+5=13
...

其次，如果距离为(2)的两点之间还有一条边，那么好像能够添成一个完全图……

然后就不会写了(卒

结论

如果该图为二分图，则最多能在所有黑点和白点之间加边；

如果不为二分图，则能加成一个完全图。

证明

官方题解

假设在(s)和(t)之间存在一条长度为奇数的路径，也就是说对于某个奇数(k)，存在一个点的序列(s=v_0,v_1,...,v_k=t)((v_i)和(v_{i+1})相邻)。

如果(k=1)，那么(s)和(t)之间本身就有一条边。如果(kgeq 3)，通过在(v_{k-3})和(v_k)之间加边，我们得到了一条(s)和(t)之间长度为(k-2)的路径。通过重复这个操作，我们可以一直减少(s)和(t)之间路径的长度最后在(s)和(t)之间加一条边。

这表示了奇数长路径的重要性，以及二分图性质的重要性。

Case 1. 不是二分图

不是二分图意味着存奇数长度的环，不妨设点(v)为环中的一点。因为图是连通图，所以对于任意的点对((s,t))，总有一条路径(srightarrow vrightarrow t). 如果路径长度为偶数，则可通过加上点(v)处的奇环使得路径长度为奇数。

因此，在任意两点间都能找到一条奇数长度的路径，故可以将图加成一个完全图。所以答案为(N(N-1)/2-M).

Case 2. 是二分图

这种情况下，可以将点染成黑点和白点，每条边连接着一个白点和一个黑点。考虑任意的黑点和白点，因为图是连通图，所以黑点(b)和白点(w)之间存在着一条路径，并且显然路经长为奇数。因此，可以在(b)和(w)之间加边。另一方面，在同种颜色的点之间绝对无法加边。

故答案为(BW-M)，(B)为白点个数，(W)为黑点个数。

具体写法

二分图的充要条件：所有回路长度均为偶数

法一：(dfs)
模拟染色看是否一个顶点会染到不同的颜色

法二（很新颖）：并查集
具体解释见noip 2010 关押罪犯这道题的并查集做法

Code

Ver. 1 dfs

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
struct Edge {
    int to, ne;
    Edge(int _to=0, int _ne=0): to(_to), ne(_ne) {}
}edge[maxn*2];
int tot, ne[maxn];
void add(int u, int v) {
    edge[tot] = Edge(v, ne[u]);
    ne[u] = tot++;
}
int n, m, c[maxn];
void dfs(int u, int col) {
    c[u] = col;
    for (int i = ne[u]; ~i; i = edge[i].ne) {
        int v = edge[i].to;
        if (c[v] == -1) dfs(v, !col);
        if (c[v] != !col) { printf("%lldn", 1LL*n*(n-1)/2-m); exit(0); }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    memset(c, -1, sizeof(c));
    memset(ne, -1, sizeof(ne));
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    int b=0, w=0;
    for (int i = 1; i <= n; ++i) if (c[i]) ++b; else ++w;
    printf("%lldn", 1LL*b*w-m);
    return 0;
}

Ver. 2 并查集

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long LL;
int fa[maxn], sz[maxn];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool same(int u, int v) { return find(u) == find(v); }
void unionn(int x, int y) {
    x = find(x), y = find(y);
    if (sz[x] > sz[y]) swap(x, y);
    fa[x] = y; sz[y] += sz[x];
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= (n<<1); ++i) fa[i] = i;
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        unionn(u, n+v);
        unionn(n+u, v);
    }
    for (int i = 1; i <= n; ++i) if (same(i, n+i)) { printf("%lldn", 1LL*n*(n-1)/2-m); return 0; }
    int b = 1, w = 0;
    for (int i = 2; i <= n; ++i) if (same(1, i)) ++b; else ++w;
    printf("%lldn", 1LL * b * w - m);
    return 0;
}