[kuangbin带你飞] 题单 最短路问题 + 并查集问题 https://blog.csdn.net/m0_46272108/article/details/108923142
带权并查集 + 离散化问题 有一个由0，1组成的数字串，现在你问一个人。他会告诉你这一个数字串中第i位到第j位的1的个数为奇数还是偶数。 看哪个人说的是错的。 数据比较大，这里要用离散化来处理数据，用map
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<map> #include<algorithm> #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ll long long //#define int ll #define INF 0x3f3f3f3f using namespace std; int read() { int w = 1, s = 0; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * w; //最大公约数 }int gcd(int x,int y) { if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后 //递归终止条件千万不要漏了，辗转相除法 return x % y ? gcd(y, x % y) : y; } int lcm(int x,int y)//计算x和y的最小公倍数 { return x * y / gcd(x, y);//使用公式 } //------------------------ 以上是我常用模板与刷题几乎无关 ------------------------// #define RP(i,s,t) for(int i=s;i<=t;i++) #define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); const int N = 10010; int p[N];//父节点 int w[N];//权值 map<int, int>Map; int find(int x){ if(x == p[x]) return x; int tmp = p[x]; p[x] = find(p[x]); //带权并查集关系的转移 w[x] = (w[x] + w[tmp] + 2) % 2; return p[x]; } bool Union(int a, int b, int x){ int pa = find(a), pb = find(b); if (pa != pb) { p[pa] = pb; w[pa] = (w[a] - w[b] + x + 2) % 2; //与之前建立的关系奇偶性不符，则表示出现冲突 } else if ((w[a] - w[b] + 2) % 2 != x) { return false; } return true; } int main() { int n = read(), m = read(); for(int i = 1; i <= N; ++i) { p[i] = i, w[i] = 0; } int ans=0, tot = 0; for (int i = 1; i <= m; ++i) { int a = read(), b = read(); string s; cin >> s; //由于前缀和的奇偶性，这里a要记得-1 --a; //map用来离散化 if (!Map[a]) Map[a] = ++tot; if (!Map[b]) Map[b] = ++tot; int flag; if (s == "odd") { flag = 1; } else { flag = 0; } if(Union(Map[a], Map[b], flag)) ans++; else break; } printf("%d\n", ans); }