The article directories
 Take weights and look up sets
 Type and look up set
 sample

 Analysis of the
 code
 summary
Take weights and look up sets
A weighted union lookup set is a node with weight information. The weight makes the relationship quantifiable, that is to say, the weight represents a certain relationship between the current node and the parent node, through which the relationship between the two nodes under the same tree can also be expressed. And the general parallel lookup set can only be judged to belong to a certain set.
Type and look up set
It is possible to judge whether a relationship is a relationship or not, for example, a friend’s friend is a friend. But for example, if the enemy’s enemy is a friend and there are more than two kinds of relationships, you can use category union lookup, and you can use multiple sets of union lookup to simulate categories.
sample
Portal: POJ1401
There are three groups of animals in the animal kingdom, A,B, and C, and they form interesting loops in the food chain. A eats B, B eats C, C eats A. There are N animals, numbered 1n. Every animal is one of A,B, or C, but we don’t know which one it is. There are two ways to describe the relationship between these N animals in the food chain. The first way is “1 X Y”, which means X and Y are of the same kind. The second way to say it is “2 X Y”, which means X eats Y. He said K statements, one after the other, some true and some false, to N animals, using the two statements. When a statement satisfies one of the following three, it is a lie, otherwise it is a truth. 1) The current statement conflicts with some of the previous true statements. 2) If X or Y is greater than N, it is false. 3) The current statement means X eats X, which is a lie. Your task is to output the total number of lies given N (1 <= N <= 50,000) and K sentences (0 <= K <= 100,000).
input:
The first line is two integers N and K separated by a space. The following K lines are three positive integers D, X, and Y, separated by a space, where D indicates the type of statement. If D=1, then X and Y are homogeneous. If D=2, X eats Y.
output:
There is only one integer to indicate the number of lies.
Sample Input:
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
Copy the code
Sample Output:
3
Copy the code
Analysis of the
 The weighted and lookup set method defines the weight array rela[] to describe the relationship with the root node, where 0 means like, 1 means the current point can eat others, and 2 means the current point is eaten by others. The relationship between root[] and rela[] is maintained through vector thought to judge whether it is contradictory to the previous relationship. Ps: Detailed vector diagram
 Open an array of size 3n, using x, x+n, x+2n to represent three different types. For example, x+n is the natural enemy of X, x+2n is the natural enemy of x+n, x is the natural enemy of x+2n and then you can simulate and maintain the array and decide. (Of course, it is also possible to represent prey, the natural enemy of source code)
code
 Weighted and search set solution
#include<cstdio>
using namespace std;
const int maxn = 50004;
int root[maxn], rela[maxn];
int r, x, y, n, k;
int Find(int x) {
if (x == root[x])return x;
int tmp = root[x];
root[x] = Find(root[x]);// Compression path
// Relationship between x and root = relationship between x and parent + relationship between parent (TMP) and root
rela[x] = (rela[x]+rela[tmp]+ 3) % 3;
return root[x];
}
bool check(int r, int x, int y) {
if (x > n  y > n  (r == 1 && x == y))
return false;
if (Find(x) == Find(y))
// (r = x to the root + y to the root) (~rela[y])
return r == (rela[x]  rela[y] + 3) % 3;
else return true;
}
void Union(int r, int x, int y) {
int fx = Find(x), fy = Find(y);
if(fx ! = fy) { root[fx] = fy;// the x root merges into the y root set
// Update x root to new root
// The relationship between x and the new root = the relationship between the root and x (~relx[x])+ the relationship between x and y (r)+ the relationship between y and the root
rela[fx] = (rela[x] + r + rela[y] + 3) % 3; }}int main(a) {
scanf("%d%d", &n, &k);
for (int i = 0; i <= n; i++) {/ / initialization
root[i] = i;
rela[i] = 0;
}
int ans = 0;
while (k) {
scanf("%d%d%d", &r, &x, &y);
r;
if (check(r, x, y))
Union(r, x, y);
else ans++;
}
printf("%d\n", ans);
return 0;
}
Copy the code
 Class and search set solution
#include<cstdio>
using namespace std;
const int maxn = 50004;
int root[maxn * 3];
int r, x, y, n, k;
int Find(int x) {
return x == root[x] ? x : root[x] = Find(root[x]);
}
bool check(int r, int x, int y) {
if (x > n  y > n  (r == 1 && x == y))
return false;
int fx = Find(x), fy = Find(y);
int fyn = Find(y + n);
int fynn = Find(y + n + n);
if (r == 0) {/ / the same kind
if (fx == fyn  fx == fynn)
return false;
}
else {/ / x y
if (fx == fy  fx == fynn)
return false;
}
return true;
}
void Union(int r, int x, int y) {
int fx = Find(x), fy = Find(y);
int fxn = Find(x + n), fyn = Find(y + n);
int fxnn = Find(x + n + n), fynn = Find(y + n + n);
if(fx ! = fy) {if (r == 0) {//x is the same as y
root[fx] = fy; // The class of x and the class of y are the same
root[fxn] = fyn; // The natural enemies of X and Y are of the same kind
root[fxnn] = fynn;// X's prey is of the same species as Y's prey
}
else {/ / x y
root[fx] = fyn; // X's kindred and Y's natural enemy are kindred
root[fxn] = fynn;// X's natural enemies are of the same species as Y's prey
root[fxnn] = fy; // X's prey is of the same species as Y's}}}int main(a) {
scanf("%d%d", &n, &k);
for (int i = 0; i <= 3 * n; i++)root[i] = i;/ / initialization
int ans = 0;
while (k) {
scanf("%d%d%d", &r, &x, &y);
r;
if (check(r, x, y))
Union(r, x, y);
else ans++;
}
printf("%d\n", ans);
return 0;
}
Copy the code
summary
 If there are too many relationships (categories), then category and set lookup is cumbersome to write, and weighted and set lookup is more dominant.
 Category and search set also need enough space, the space limit is small problem is also hard.
 However, category and set searching is easier to understand and simulate, and weighted and set searching requires a full understanding of its vector thinking.
Original is not easy, please do not reprint (this is not rich visits add insult to injury) blogger home page: blog.csdn.net/qq_45034708 If the article is helpful to you, remember to focus on the likes collection ❤