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: POJ-1401

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 1-n. 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

  1. The weighted and look-up 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
  2. 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

  1. 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
  1. 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

  1. If there are too many relationships (categories), then category and set lookup is cumbersome to write, and weighted and set lookup is more dominant.
  2. Category and search set also need enough space, the space limit is small problem is also hard.
  3. 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 ❤