Luogu p2024 [noi2001] food chain

[NOI2001] The food chain

Portal

Title Description

There are three kinds of animals in the animal kingdom A,B,C, The food chain of these three kinds of animals forms an interesting ring .A eat B,B eat C,C eat A.

existing N Animals , With 1 － N Number . Every animal is A,B,C One of the , But we don't know which one it is .

There are two ways of saying it N Describe the food chain of animals ：

• The first is 1 X Y, Express X and Y It's the same kind .
• The second is 2 X Y, Express X eat Y .

This man is right N Animals , Use the two statements above , Say... Sentence by sentence K Sentence , this K Some sentences are true , Some are fake . When a sentence satisfies one of the following three , This is a lie , Otherwise, it's the truth .

• The current words conflict with some of the real words in front , It's a lie
• In the current conversation X or Y Than N Big , It's a lie
• The current words mean X eat X, It's a lie

Your task is based on the given N and K Sentence , The total number of output lies .

Input format

The first line has two integers ,N,K, Express N Animals ,K Sentence .

The second line begins with a sentence in each line （ According to the title , See Example ）

Output format

a line , An integer , The total number of lies .

Examples #1

The sample input #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

Sample output #1

3

Tips

1 ≤ N ≤ 5 ∗ 10^4
1 ≤ K ≤ 10^5

Take the right and check the collection

pre[i]： Record i Our ancestors
dis[i]：i and Its ancestral relationship
0 Represents the same kind as above ,1 On behalf of predators ,2 Represents being preyed on by the above
But if the path is compressed ,dis The relationship between representatives is invalid , So we need to update the relationship ,dis[x] = (dis[pre[x]] + dis[x]) % 3;, This can still represent the relationship with the father node .== +3 After that %, Just because I'm afraid of negative numbers ==
After path compression , In addition to the ancestral node , Each point points directly to the ancestor node of its own set , And it has a fixed relationship with the ancestor node
We calculate from vectors
If it doesn't matter , Not the same set , To merge , It requires the relationship between the two ancestor nodes

If it is the same set , The same root node is connected , It requires a direct relationship between two nodes

/** * @author Changersh * @date 2022/7/23 11:22 * 0  similar ,1  Prey on the top ,2  Be preyed on by the above  */

import java.util.*;
import java.lang.*;
@SuppressWarnings({
    "all"})
public class Main {
    
    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        //  initialization 
        for (int i = 1; i <= n; i++) pre[i] = i;
        Arrays.fill(dis, 0);

        int cnt = 0;
        while (k-- > 0) {
    
            int opt = scanner.nextInt();
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            if (x > n || y > n) {
     //  It's not this  n  Animals 
                cnt++;
                continue;
            }
            int fx = find(x), fy = find(y);
            if (opt == 1) {
     // x y  It's the same kind 
                if (fx == fy && dis[x] != dis[y]) {
     //  Two people in the same set , But the relationship with the root node is different , Different kinds 
                    cnt++; //  Falsehood 
                    continue;
                }
                else {
     //  In a different set , Explain that there was no relationship before , Merge two people 
                    pre[fx] = fy;
                    dis[fx] = (0 + dis[y] - dis[x] + 3) % 3; //  according to xy Congeneric relationship , Calculate the relationship of the root node 
                }
            }
            else {
      // x  eat  y
                if (fx == fy && (dis[x] - dis[y] + 3) % 3 != 1) {
    
                    //  Belong to the same set , But not predation , It's a lie 
                    cnt++;
                    continue;
                }
                else {
     //  If not in the same set , It's the truth , Merge 
                    pre[fx] = fy;
                    dis[fx] = (dis[y] + 1 - dis[x] + 3) % 3;
                }
            }
        }
        System.out.println(cnt);
    }
    private static int[] pre = new int[50005];
    private static int[] dis = new int[50005];
    private static int find(int x) {
    
        if (pre[x] != x) {
    
            int u = find(pre[x]);
            dis[x] = (dis[pre[x]] + dis[x]) % 3;
            pre[x] = u;
        }
        return pre[x];
    }
}

Type and search

Open three times the size ,1 - n It's the same kind ,n+1 - 2n It's prey ,2n+1 - 3n They're natural enemies
Then it was discussed according to the situation , Look at the code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include<unordered_map>
#include <unordered_set>

using namespace std;

//  Type and search set writing 
const int maxN = 5e4 + 5;
int pre[maxN * 3], n, k, ans; //  Three times pre size ,1  It's the same kind ,2  It's prey ,3  They're natural enemies 

int find(int x) {
     return pre[x] == x ? pre[x] : find(pre[x]); }

int main() {
    
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n * 3; i++) pre[i] = i; //  initialization 
	
	for (int i = 1; i <= k; i++) {
    
		int opt, x, y;
		scanf("%d %d %d", &opt, &x, &y);
		if (x > n || y > n) {
     //  It's not this  n  Animals 
			ans++;
			continue;
		}
		
		if (opt == 1) {
     //  Case one ,x y  It's the same kind 
			if ((find(x + n) == find(y)) || (find(x + 2 * n) == find(y))) {
     // y yes  x  Prey or similar , The explanation is a lie 
				ans++;
			} else {
    
				pre[find(x)] = find(y);                 // x y  It's the same kind 
				pre[find(x + n)] = find(y + n);         // x  Prey of   yes  y  Prey of 
				pre[find(x + 2 * n)] = find(y + 2 * n); // x  The natural enemies of   yes  y  The natural enemies of 
			}
		} else {
     //  The second case ,x  eat  y
			if ((find(x) == find(y)) || (find(x + 2 * n) == find(y))) {
     // x y  It's the same kind , perhaps  y  yes  x  The natural enemies of , It's a lie 
				ans++;
			} else {
    
				pre[find(x + n)] = find(y);         // x  Prey of   yes  y  The same kind of 
				pre[find(x + 2 * n)] = find(y + n); // x  The natural enemies of   yes  y  Prey of 
				pre[find(x)] = find(y + 2 * n);     // x  The same kind of   yes  y  The natural enemies of 
			}
		}
	}
	
	printf("%d\n", ans);
	return 0;
}