Comprehensive example: poj 1182 food chain http://poj.org/problem?id=1182

There are three kinds of animals A, B and C in the animal kingdom. The food chain of these three kinds of animals is: A eats B, B eats C, and C eats A.

there are N animals, numbered by 1~N. Every animal is one of A, B and C, but we don't know which one it is.

some people describe the food chain relationship formed by these N animals in two ways:

the first expression is "1 X Y", which means that X and Y are of the same kind.

the second expression is "2 X Y", which means that X eats Y.

the man used the above two statements to say K sentences sentence by sentence to N animals. Some of these K sentences are true and some are false. When a sentence meets one of the following three requirements, it is false, otherwise it is true.

1) the current words conflict with some of the previous true words, which is false;

2) if X or Y is greater than N in the current words, it is a lie;

3) the current words mean that X eats X, which is a lie.

your task is to output the total number of falsehoods according to the given N (1 < = N < = 50000) and K sentences (0 < = k < = 100000).

Code:

#include <iostream> #include <stdio.h> using namespace std; const int maxn = 50005; int s[maxn]; //aggregate int d[maxn]; // 0: similar; 1: Eat; 2: Be eaten int ans; void init_set(){ //initialization for(int i = 0; i <= maxn; i++) { s[i] = i; d[i] = 0; } } int find_set(int x){ //Path compression with weights if(x != s[x]) { int t = s[x]; //Record parent node s[x] = find_set(s[x]); //Path compression. The last return of recursion is the root node d[x] = (d[x] + d[t]) % 3; //The weight is updated to the weight from x to the root node } return s[x]; } void merge_set(int x, int y, int relation){ //merge int rootx = find_set(x); int rooty = find_set(y); if (rootx == rooty){ if ((relation - 1) != ((d[x] - d[y] + 3) % 3)) //Judgment contradiction ans++; } else { s[rootx] = rooty; //merge d[rootx] = (d[y] - d[x] + relation - 1) % 3; //Update weight } } int main(){ int n, k; cin >> n >> k; init_set(); ans = 0; while (k--){ int relation, x, y; scanf("%d%d%d",&relation,&x,&y); if ( x > n || y > n || (relation == 2 && x == y ) ) ans++; else merge_set(x,y,relation); } cout << ans; return 0; }

Code analysis: the parallel search board is nothing more than three points: 1 Initialization. 2. find the parent node. 3. merger.

This problem adopts optimization, that is, path compression.

void init_set(){ //initialization for(int i = 0; i <= maxn; i++) { s[i] = i; d[i] = 0; } }

Initialization needless to say, the initial parent node of each point is itself. This problem is weighted, so you have to initialize the weight as;

int find_set(int x){ //Path compression with weights if(x != s[x]) { int t = s[x]; //Record parent node s[x] = find_set(s[x]); //Path compression. The last return of recursion is the root node d[x] = (d[x] + d[t]) % 3; //The weight is updated to the weight from x to the root node } return s[x]; }

Function to find the parent node: this point is also an optimization point. The parent node of the node is updated during the query until the parent node of the node is the root node. In this way, the root node can be found directly during the next search. The weight is also updated to the weight of the root node. The remaining 3 are required for the topic.

void merge_set(int x, int y, int relation){ //merge int rootx = find_set(x); int rooty = find_set(y); if (rootx == rooty){ if ((relation - 1) != ((d[x] - d[y] + 3) % 3)) //Judgment contradiction ans++; } else { s[rootx] = rooty; //merge d[rootx] = (d[y] - d[x] + relation - 1) % 3; //Update weight } }

The merge code is also the core code. First, find the root node of the 2 nodes. If the root nodes are the same, it indicates that the two nodes have a relationship. Next, judge whether their relationship is contradictory. The statement to judge the contradiction is derived from paper. If the root nodes are different, merge and update the weights. The code for updating the weights should also be derived according to the meaning of the topic.

The consolidation process can also be optimized

When merging elements x and y, first find their root nodes, and then merge the two root nodes, that is, change the set of one root node to another. The height of these two root nodes is different. If the set with smaller height is merged into the set with larger height, the height of the tree can be reduced.