样例输入 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 样例输出 3

解析

我看了这个题的解析，便深刻地了解到并查集的用处了。 一般来说，并查集可以维护两种集合，即是或不是亲戚，但对于这个题，需要有的是三个集合，即自身，天敌，猎物。很显然，一般的并查集不行。便有了新的东西——种类并查集。 详见该大佬的文章： https://blog.csdn.net/fkjslee/article/details/48810429

接下来详细讲解1-n为什么要扩大到1-3n

首先说明本题的解法是将1-n个元素扩大为1-3n个元素，使用[1，3n]个并查集（每一个并查集中的所有元素都具有同一种特性，不同并查集中不存在相同元素）来维护3n元素彼此的关系。 在这里我们留下两个问题：1.为什么是[1,3n]个并查集？2.为什么要有3n个元素？

听不懂，很正常，往下看。

在这里x元素，x+n元素，x+2n元素三者的关系被定义为： x∈[1，n]–x元素的同类 x∈[n+1，2n]–x元素的天敌 x∈[2n+1，3n]–x元素的猎物

至于为什么这么定义，可以先当作留下的第3个问题。

这时我们来分析一下上面定义的作用 我们可以通过x+n元素来确定x元素目前已知的天敌，也可以通过x+2n元素来确定x元素目前的猎物，还可以通过x元素本身来确定x的同类

则判断真假要有以下几个原则：

1.两个同类元素的天敌集合是同一个集合，猎物集合也是同一个集合 2.天敌的天敌是猎物 3.猎物的猎物是天敌

那么就不难得出对于一句真话，当x元素,y元素是同类时，将他们两者的天敌集合（x+n元素与y+n元素所在集合）和猎物集合（x+2n元素与y+2n元素所在集合）以及自身所在的集合分别合并。当x元素是y元素的天敌时，将x元素所在集合与y元素的天敌集合合并，将y元素所在集合和x元素的猎物集合合并，将x元素的天敌集合和y元素的猎物集合合并

放代码

//x是本身，x+n是天敌，x+2n是猎物 #include<bits/stdc++.h> using namespace std; int n,m,ans=0; int f[150001]; int find(int t){return f[t]==t ? f[t] : f[t]=find(f[t]);} void work(int x,int y){f[find(x)]=f[find(y)];} int main() { cin>>n>>m; for(int i=1;i<=n*3;i++) f[i]=i; for(int i=1;i<=m;i++) { int a,x,y; cin>>a>>x>>y; if(x>n||y>n) ans++; else { if(a==1) { if(find(x+n)==find(y)||find(x+n*2)==find(y)) ans++; else work(x,y),work(x+n,y+n),work(x+n*2,y+n*2); } else { if(x==y||find(x)==find(y)||find(x+n)==find(y)) ans++; else work(x,y+n),work(x+2*n,y),work(x+n,y+2*n); } } } cout<<ans<<endl; return 0; }

那么现在回答上面3个问题。

种类并查集就是这么做的，就是这么个做法。

为什么要这样做？”是我们在学习中最常遇到的问题，但有时候这个问题真的很恐怖。就如同我们知道1+1=2，但是当你产生“”为什么1+1=2”这样一个问题时就会感到恐惧，因为你发现你是在质疑规则，但规则是不能被撼动的，否则一切都会消失，所以你的问题将永远无法得到解答，于是乎你就会掉入思维的无底洞。

学习的过程是打破砂锅问到底，但你最好祈祷你自己不会打破砂锅，因为根本没有底。

ps.该篇题解深受洛谷大佬NS·YJD的影响。