带边权
/*
知识点-前缀和+模二意义下加法等价于按位与+离散化+并查集
1. s[l, r]中有奇数个1,等价于s(l-1)与s(r)的奇偶性不同
2. s[l, r]~偶数~,~相同
3. d[x]-表示x与p[x]之间的关系,
d[x]=0,x与p[x]奇偶性相同
d[x]=1,~不同
4. 任意d[x],d[y],
若d[x]+d[y]为奇数-d[x],d[y]奇偶性不同
~为偶数,~相同
5. 离散化取的是(a-1)与b的值
6. t=0-代表s(a-1)与s(b)奇偶性相同
t=1-代表~不同
7. find(),用来更新某一个节点x与根节点的关系(d[x],p[x])
8. 如何发现矛盾,
当pa和pb奇偶性相同时,此时判断d[x]^d[y]与t的关系
若不等则矛盾输出当前出问题的前一个节点
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e5+10;
int n, m;
int p[N], d[N];
unordered_map<int, int> S;
int get(int x) {
if(S.count(x) == 0) S[x] = ++n;
return S[x];
}
int find(int x) {
if(p[x] != x) {
int root = find(p[x]);
d[x] ^= d[p[x]];
p[x] = root;
}
return p[x];
}
int main() {
cin >> n >> m;
n = 0;
for(int i = 0; i < N; i++) p[i] = i;
int res = m;
for(int i = 1; i <= m; i++) {
int a, b;
string type;
cin >> a >> b >> type;
a = get(a-1), b = get(b);
int t = 0;
if(type == "odd") t = 1;
// t=0-代表s(a-1)与s(b)奇偶性相同
// t=1-代表~不同
int pa = find(a), pb = find(b);
if(pa == pb) {
if((d[a] ^ d[b]) != t) {
res = i - 1;
break;
}
} else {
p[pa] = pb;
d[pa] = d[a] ^ d[b] ^ t;
}
}
cout << res << endl;
return 0;
}
扩展域
/*
带权并查集
知识点-前缀和+模二意义下加法等价于按位与+离散化+并查集
1. s[l, r]中有奇数个1,等价于s(l-1)与s(r)的奇偶性不同
2. s[l, r]~偶数~,~相同
3. d[x]-表示x与p[x]之间的关系,
d[x]=0,x与p[x]奇偶性相同
d[x]=1,~不同
4. 任意d[x],d[y],
若d[x]+d[y]为奇数-d[x],d[y]奇偶性不同
~为偶数,~相同
5. 离散化取的是(a-1)与b的值
6. t=0-代表s(a-1)与s(b)奇偶性相同
t=1-代表~不同
7. find(),用来更新某一个节点x与根节点的关系(d[x],p[x])
8. 如何发现矛盾,
当pa和pb奇偶性相同时,此时判断d[x]^d[y]与t的关系
若不等则矛盾输出当前出问题的前一个节点
扩展域
注意x不是代表一个变量,而是一个属性x为奇数
x代表x是偶数
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 4e5+10, M = N / 2;
int n, m;
int p[N], d[N];
unordered_map<int, int> S;
int get(int x) {
if(S.count(x) == 0) S[x] = ++n;
return S[x];
}
int find(int x) {
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
cin >> n >> m;
n = 0;
for(int i = 0; i < N; i++) p[i] = i;
int res = m;
for(int i = 1; i <= m; i++) {
int a, b;
string type;
cin >> a >> b >> type;
a = get(a-1), b = get(b);
if(type == "even") {
if(find(a+M) == find(b)) {
res = i - 1;
break;
}
p[find(a)] = p[find(b)];
p[find(a+M)] = p[find(b+M)];
} else {
if(find(a) == find(b)) {
res = i - 1;
break;
}
p[find(a+M)] = p[find(b)];
p[find(a)] = p[find(b+M)];
}
}
cout << res << endl;
return 0;
}