poj1182食物链（并查集经典题）

食物链

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 124632 Accepted: 38129
Description

动物王国中有三类动物A,B,C&＃xff0c;这三类动物的食物链构成了有趣的环形。A吃B&＃xff0c; B吃C&＃xff0c;C吃A。
现有N个动物&＃xff0c;以1&＃xff0d;N编号。每个动物都是A,B,C中的一种&＃xff0c;但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述&＃xff1a;
第一种说法是"1 X Y"&＃xff0c;表示X和Y是同类。
第二种说法是"2 X Y"&＃xff0c;表示X吃Y。
此人对N个动物&＃xff0c;用上述两种说法&＃xff0c;一句接一句地说出K句话&＃xff0c;这K句话有的是真的&＃xff0c;有的是假的。当一句话满足下列三条之一时&＃xff0c;这句话就是假话&＃xff0c;否则就是真话。
1&＃xff09; 当前的话与前面的某些真的话冲突&＃xff0c;就是假话&＃xff1b;
2&＃xff09; 当前的话中X或Y比N大&＃xff0c;就是假话&＃xff1b;
3&＃xff09; 当前的话表示X吃X&＃xff0c;就是假话。
你的任务是根据给定的N&＃xff08;1 <&＃61; N <&＃61; 50,000&＃xff09;和K句话&＃xff08;0 <&＃61; K <&＃61; 100,000&＃xff09;&＃xff0c;输出假话的总数。
Input

第一行是两个整数N和K&＃xff0c;以一个空格分隔。
以下K行每行是三个正整数 D&＃xff0c;X&＃xff0c;Y&＃xff0c;两数之间用一个空格隔开&＃xff0c;其中D表示说法的种类。
若D&＃61;1&＃xff0c;则表示X和Y是同类。
若D&＃61;2&＃xff0c;则表示X吃Y。
Output

只有一个整数&＃xff0c;表示假话的数目。
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


Sample Output

3


分析&＃xff1a;

本题是并查集的经典题目&＃xff0c;对于有冲突的话语需要通过并查集来进行判断。

并查集可以看成集合&＃xff0c;集合之间的元素具有某种关系。并查集涉及的操作主要是集合的合并和查询根结点&＃xff0c;这里的集合其实就是一条食物链&＃xff0c;该集合里面的元素之间存在某种关系&＃xff0c;而在存储的时候直接存的是每个结点与根节点的关系&＃xff0c;而结点之间的关系则需要公式。那什么时候是当前的话与前面的话有冲突呢&＃xff1f;就是
1 若输入1 x y&＃xff0c;表明x、y是同类&＃xff0c;则它们与根结点的关系必定相同&＃xff0c;若不同则说明有冲突。
2 若输入2 x y&＃xff0c;表明x、y存在x吃y的关系&＃xff0c;则它们在同一条食物链&＃xff0c;且x、y两个结点之间有x吃y的关系&＃xff0c;如果不是&＃xff0c;则说明有冲突。

这里的并查集不仅需要保存结点&＃xff0c;还需要保存集合中每个结点与根结点的关系。 难点就是在合并和路径压缩时&＃xff0c;怎么改变结点与根结点的关系。 首先来看一下集合之间元素关系转换&＃xff0c;看懂这个对后面有一定帮助。

集合之间元素关系转换

这里有A、B、C三类动物&＃xff0c;它们之间的关系如下。这里给出两个表格&＃xff0c;先简单明确一下存在的关系&＃xff0c;以及关系之间的转换。

参考下表&＃xff0c;可以知道如果已知A、B关系&＃xff0c;B、C关系&＃xff0c;如何得出A、C关系。如果把B看作根结点&＃xff0c;A、B看作集合中的两个结点&＃xff0c;已知A、B与分别C的关系&＃xff0c;如何得到集合中任意两个元素A、B之间的关系&＃xff1f;

我们假设r[A]存的是A->B的关系&＃xff0c;r[C]存的是C->B的关系&＃xff0c;那A->C的关系其实就是(A->B&＃43;B->C)%3,也就是(r[A]&＃43;3-r[C])%3.(B看作根结点&＃xff0c;如果C->B关系为r[C]&＃xff0c;则B->C关系为(3-r[C])%3. )
参考上面那个表的信息&＃xff0c;可以知道表达式是正确的。

路径压缩

下面这张图的意思其实就是如果要把A的根结点变为C&＃xff0c;那么A与C的关系就是A与其父节点B的关系&＃xff0c;再加上父节点B与根结点C的关系。这样转换的原因是我们存储的是结点与根结点的关系&＃xff0c;路径压缩后根结点发生了变化&＃xff0c;结点与根结点的关系自然也要发生变化

合并集合

合并结合是比较难的。
假如我们有x、y两个集合&＃xff0c;它们的根结点分别是a和b&＃xff0c;我们是这样合并的&＃xff1a;把集合x并入集合y&＃xff0c;也就是令集合x的根结点a指向b&＃xff0c;构成一个新集合&＃xff0c;根结点为b。这里就涉及一个问题&＃xff0c;我们需要知道a到b的关系。
已知的关系是x->a&＃xff1a;r[x]和y->b:r[y]&＃xff0c;还有x->y的关系h,
可以知道a->b&＃61; a->x &＃43; x->b &＃61; a->x &＃43; h &＃43; y->b .
也就是a->b&＃61;(3-r[x]&＃43;h&＃43;r[y])%3

代码&＃xff1a;

#include
#include
using namespace std;
const int N&＃61;50001;
int p[N],r[N];
int find(int i){int t;if(i&＃61;&＃61;p[i]) return i;t&＃61;p[i];p[i]&＃61;find(p[i]);//路径压缩r[i]&＃61;(r[t]&＃43;r[i])%3;//更改关系return p[i];
}
void merge(int x,int y,int h)
{int a&＃61;find(x),b&＃61;find(y);p[a]&＃61;b;r[a]&＃61;(r[y]-r[x]&＃43;3&＃43;h)%3;
}//合并集合
int main()
{int n,k,i,ans&＃61;0;scanf("%d %d",&n,&k);for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;) p[i]&＃61;i;while(k--){int d,x,y;scanf("%d %d %d",&d,&x,&y);if(x>n||y>n){ans&＃43;&＃43;;continue; }if(d&＃61;&＃61;1){if(find(x)&＃61;&＃61;find(y)){if(r[x]!&＃61;r[y]) ans&＃43;&＃43;;}else merge(x,y,0);}else{if(find(x)&＃61;&＃61;find(y)){//if(r[x]!&＃61;(r[y]&＃43;1)%3) ans&＃43;&＃43;;if((r[x]&＃43;3-r[y])%3!&＃61;d-1) ans&＃43;&＃43;;}else merge(x,y,1);}}printf("%d\n",ans);return 0;
}


更多&＃xff1a;

下面这个博客的讲解也很不错&＃xff1a;
https://blog.csdn.net/niushuai666/article/details/6981689