Codeforces Round 680 (Div. 1)___C. Team-Building —— 可撤销并查集 + 判奇环

92 阅读 0 评论 61 点赞

我是靠谱客的博主文艺夕阳，这篇文章主要介绍Codeforces Round 680 (Div. 1)___C. Team-Building —— 可撤销并查集 + 判奇环，现在分享给大家，希望可以做个参考。

题目链接：点我啊╭(╯^╰)╮

题目大意：

     $n$ 个点， $m$ 条边的无向图，每个点都属于一个组
    选取两个组的所有点，这些点组成的图无奇环
    问有多少组对满足要求

解题思路：

    考虑求有多少非法组对
    是否存在奇环的判断方法可以用并查集：
    对于边 $(u, v)$ ，将 $u$ 与 $v + n$ 合并， $v$ 与 $u + n$ 合并
    若存在边 $(u, v)$ 已经在同一个集合里了，则说明存在奇环

    对于同一组的所有点，直接按上述方法判断
    对于不同组，一条边若连接了组 $u$ 与组 $v$ ，则将所有连接了组 $u$ 与组 $v$ 的边放到一起
    然后将这些边一起加上，用上述方法判断是否存在奇环
    判断完后再撤销这些并查集，判断另外两组
    这样保证判断不会重复

复制代码

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 1e6 + 5;
int n, m, k, a[maxn], b[maxn];
int ji[maxn], c[maxn], ans;
map <pii, int> mp;
vector <int> g[maxn];
struct USF {
struct Stack {
int u, v, rk;
} st[maxn];
int fa[maxn], rk[maxn], top;
inline void init() {
top = 0;
for(int i=1; i<=n*2; i++) fa[i] = i, rk[i] = 0;
}
inline int getf(int x) {
return x == fa[x] ? x : getf(fa[x]);
}
inline bool merge(int u, int v) {
int fu = getf(u), fv = getf(v);
if(fu == fv) return false;
if(rk[fu] > rk[fv]) swap(u, v), swap(fu, fv);
st[++top] = {fu, fv, rk[fv]};
fa[fu] = fv, rk[fv] += rk[fu] == rk[fv];
return true;
}
inline void undo(int k) {
while(k--) {
Stack &now = st[top--];
int u = now.u, v = now.v;
fa[u] = u, rk[v] = now.rk;
}
}
} t;
signed main() {
scanf("%d%d%d", &n, &m, &k);
for(int i=1; i<=n; i++) scanf("%d", c+i);
t.init();
for(int i=1; i<=m; i++) {
scanf("%d%d", a+i, b+i);
if(c[a[i]] != c[b[i]]) continue;
int fu = t.getf(a[i]), fv = t.getf(b[i]);
if(fu == fv) ji[c[a[i]]] = 1;
else t.merge(a[i], b[i]+n), t.merge(b[i], a[i]+n);
}
int tot = 0;
for(int i=1; i<=m; i++) {
if(c[a[i]] == c[b[i]]) continue;
if(ji[c[a[i]]] || ji[c[b[i]]]) continue;
int u = c[a[i]], v = c[b[i]];
if(u > v) swap(u, v);
if(mp.count({u, v})) g[mp[{u, v}]].push_back(i);
else g[mp[{u, v}]=++tot].push_back(i);
}
for(auto i : mp) {
int now = t.top, id = i.second;
for(auto j : g[id]) {
int u = a[j], v = b[j];
int fu = t.getf(u), fv = t.getf(v);
if(fu == fv) { ans--; break; }
else t.merge(u, v+n), t.merge(v, u+n);
}
t.undo(t.top - now);
}
ll cnt = 0;
for(int i=1; i<=k; i++) cnt += !ji[i];
printf("%lldn", cnt*(cnt-1)/2+ans);
}

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
#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 1e6 + 5;
int n, m, k, a[maxn], b[maxn];
int ji[maxn], c[maxn], ans;
map <pii, int> mp;
vector <int> g[maxn];
struct USF {
struct Stack {
int u, v, rk;
} st[maxn];
int fa[maxn], rk[maxn], top;
inline void init() {
top = 0;
for(int i=1; i<=n*2; i++) fa[i] = i, rk[i] = 0;
}
inline int getf(int x) {
return x == fa[x] ? x : getf(fa[x]);
}
inline bool merge(int u, int v) {
int fu = getf(u), fv = getf(v);
if(fu == fv) return false;
if(rk[fu] > rk[fv]) swap(u, v), swap(fu, fv);
st[++top] = {fu, fv, rk[fv]};
fa[fu] = fv, rk[fv] += rk[fu] == rk[fv];
return true;
}
inline void undo(int k) {
while(k--) {
Stack &now = st[top--];
int u = now.u, v = now.v;
fa[u] = u, rk[v] = now.rk;
}
}
} t;
signed main() {
scanf("%d%d%d", &n, &m, &k);
for(int i=1; i<=n; i++) scanf("%d", c+i);
t.init();
for(int i=1; i<=m; i++) {
scanf("%d%d", a+i, b+i);
if(c[a[i]] != c[b[i]]) continue;
int fu = t.getf(a[i]), fv = t.getf(b[i]);
if(fu == fv) ji[c[a[i]]] = 1;
else t.merge(a[i], b[i]+n), t.merge(b[i], a[i]+n);
}
int tot = 0;
for(int i=1; i<=m; i++) {
if(c[a[i]] == c[b[i]]) continue;
if(ji[c[a[i]]] || ji[c[b[i]]]) continue;
int u = c[a[i]], v = c[b[i]];
if(u > v) swap(u, v);
if(mp.count({u, v})) g[mp[{u, v}]].push_back(i);
else g[mp[{u, v}]=++tot].push_back(i);
}
for(auto i : mp) {
int now = t.top, id = i.second;
for(auto j : g[id]) {
int u = a[j], v = b[j];
int fu = t.getf(u), fv = t.getf(v);
if(fu == fv) { ans--; break; }
else t.merge(u, v+n), t.merge(v, u+n);
}
t.undo(t.top - now);
}
ll cnt = 0;
for(int i=1; i<=k; i++) cnt += !ji[i];
printf("%lldn", cnt*(cnt-1)/2+ans);
}