Codeforces1128D Complete Tripartite

发表于 | 更新于 | 分类于 | 阅读次数：

Codeforces1128D Complete Tripartite

Description

一个$n$个顶点，$m$条边的无向图，保证无重边与自环，不保证连通

设$v_1, v_2 \subseteq V$是两个不相交的非空点集，定义$f(v_1, v_2)$在满足以下所有条件时为真：

  • $v_1$中的点之间不存在边
  • $v_2$中的点之间不存在边
  • 对于任意分别在$v_1, v_2$中的每一对点$(x, y)$之间均有边

问能否将$V$分为三个非空的，不相交的点集$v_1, v_2, v_3$使得$f(v_1, v_2), f(v_2, v_3), f(v_1, v_3)$均为真

若能则输出每个点所在的点集，否则输出$-1$

数据范围

$3 \le n \le 10 ^ 5,\ 0 \le m \le \min(3 \cdot 10 ^ 5,\frac {n(n - 1)} {2})$

Solution

首先阐述一下官方做法的核心：和一个点$u$没有边相连的所有点都应与$u$在同一个集合中

但是这种做法细节非常多（至少对于考场上完全不注意细节的我是致命性的）

现在提供一种非常无脑、几乎没有细节的哈希做法，复杂度与标算一样，但是编写简单度把标算吊起来打

稍微思索一下可以发现的一点是：同一集合的所有点，它们有边相连的点构成的集合是相同的

然后我们可以将点的集合转变为哈希值，直接统计比较即可

下面的代码证明了这种做法能够很好地通过此题

Code

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
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long

const int N = 1e5, Base = 31, Mod = 1e9 + 7;
int n, m, cnt;
LL Hash[N + 5], Val[N + 5];
std::map <LL, int> Bel;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = Hash[0] = 1; i <= n; ++i)
        Hash[i] = Hash[i - 1] * Base % Mod;
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        Val[u] = (Val[u] + Hash[v]) % Mod;
        Val[v] = (Val[v] + Hash[u]) % Mod;
    }
    for (int i = 1; i <= n; ++i) {
        if (Val[i] == 0) return puts("-1"), 0;
        if (Bel[Val[i]] == 0) Bel[Val[i]] = ++cnt;
    }
    if (cnt != 3)
        return puts("-1"), 0;
    for (int i = 1; i <= n; ++i)
        printf("%d ", Bel[Val[i]]);
    return puts(""), 0;
}