算法1
(带权并查集) $O(Klogn)$
通过边权维护种类关系
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n, k;
int p[100010], d[100010];
int D, x, y;
int sum;
int find(int x)
{
if(p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]]; // push_down 操作
p[x] = t;
}
return p[x];
}
int main()
{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 1; i <= k; i ++ )
{
bool flag = true;
scanf("%d %d %d", &D, &x, &y);
if (x > n || y > n)
{
flag = false;
}
else{
int a = find(x), b = find(y);
if (D == 1)
{
int a = find(x), b = find(y);
if(a == b && (d[x] - d[y]) % 3) flag = false;
else if(a != b)
{
p[a] = b;
d[a] = d[y] - d[x];
}
}
else
{
if(a == b && (d[x] - d[y] - 1) % 3) flag = false;
else if(a != b)
{
p[a] = b;
d[a] = d[y] - d[x] + 1;
}
}
}
if(!flag) sum ++;
}
printf("%d", sum);
}
算法2
(扩展域并查集) $O(Klogn)$
拆成三个域,分析其种类关系进行合并即可。
域要开三倍大小
$[1 , n]$
$[n + 1 , 2n]$
$[2n + 1 , 3n]$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 150010;
int n, m;
int D, x, y;
int fa[N];
int a_I, a_H, a_L;
int b_I, b_H, b_L;
int ans;
void init() {
for (int i = 1; i <= 3 * n; i ++ ) fa[i] = i;
}
int find(int x)
{
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
int merge(int a, int b)
{
a = find(a), b = find(b);
if (a != b) fa[b] = a;
}
void work_1(int a, int b)
{
a_I = a, a_H = a_I + n, a_L = a_H + n;
b_I = b, b_H = b_I + n, b_L = b_H + n;
if (find(a_I) == find(b_H) || find(a_I) == find(b_L)) ans ++;
else {
merge(a_I, b_I);
merge(a_H, b_H);
merge(a_L, b_L);
}
}
void work_2(int a, int b)
{
a_I = a, a_H = a_I + n, a_L = a_H + n;
b_I = b, b_H = b_I + n, b_L = b_H + n;
if (find(a_I) == find(b_I) || find(a_H) == find(b_I)) ans ++;
else {
merge(a_I, b_H);
merge(a_H, b_L);
merge(a_L, b_I);
}
}
int main()
{
scanf("%d %d", &n, &m);
init();
for (int i = 1; i <= m; i ++ )
{
scanf("%d %d %d", &D, &x, &y);
if (x > n || y > n) {
ans ++;
continue;
}
if (D == 1) work_1(x, y);
if (D == 2) work_2(x, y);
}
printf("%d", ans);
return 0;
}