首页 > 代码库 > 洛谷 P2024 食物链 POJ 1182 Label:并查集Turbo
洛谷 P2024 食物链 POJ 1182 Label:并查集Turbo
题目描述
动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。A 吃 B,B
吃 C,C 吃 A。
现有 N 个动物,以 1 - N 编号。每个动物都是 A,B,C 中的一种,但是我们并不知道
它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述:
第一种说法是“1 X Y”,表示 X 和 Y 是同类。
第二种说法是“2 X Y”,表示 X 吃 Y 。
此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真
的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
• 当前的话与前面的某些真的话冲突,就是假话
• 当前的话中 X 或 Y 比 N 大,就是假话
• 当前的话表示 X 吃 X,就是假话
你的任务是根据给定的 N 和 K 句话,输出假话的总数。
输入输出格式
输入格式:
从 eat.in 中输入数据
第一行两个整数,N,K,表示有 N 个动物,K 句话。
第二行开始每行一句话(按照题目要求,见样例)
输出格式:
输出到 eat.out 中
一行,一个整数,表示假话的总数。
输入输出样例
输入样例#1:
100 71 101 12 1 22 2 32 3 31 1 32 3 11 5 5
输出样例#1:
3
说明
1 ≤ N ≤ 5 ∗ 10^4
1 ≤ K ≤ 10^5
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int ans,N,c; 7 int father[5000005],rank[5000005]; 8 void init_(int n){ 9 for(int i=0;i<n;i++){10 father[i]=i;11 rank[i]=0;12 }13 }14 int Find(int x){15 if(father[x]==x) return x;16 else return Find(father[x]);17 }18 19 int same(int a,int b){20 return Find(a)==Find(b);21 }22 void unite(int x,int y){23 x=Find(x);24 y=Find(y);25 if(x==y) return;26 27 if(rank[x]<rank[y]){28 father[x]=y;29 }30 else{31 father[y]=x;32 if(rank[x]==rank[y]) ++rank[x];33 }34 }35 36 37 int main(){38 // freopen("01.in","r",stdin);39 scanf("%d%d",&N,&c);40 init_(3*N);41 42 for(int i=1;i<=c;i++){43 int t=0,x=0,y=0;44 scanf("%d%d%d",&t,&x,&y);45 x-=1;y-=1;46 if(x<0||N<=x||y<0||N<=y){47 ++ans;continue;48 }49 50 if(t==1){51 if(same(x,y+N)||same(x,y+2*N)){52 ans++;53 }54 else{55 unite(x,y);56 unite(x+N,y+N);57 unite(x+2*N,y+2*N);58 }59 }60 else if(t==2){61 if(same(x,y)||same(x,y+2*N)){62 ans++;63 }64 else{65 unite(x,y+N);66 unite(x+N,y+2*N);67 unite(x+2*N,y);68 }69 }70 else ans++;71 }72 printf("%d\n",ans);73 return 0;74 }用三个区域表示A B C三个种族,差不多就这样吧
洛谷 P2024 食物链 POJ 1182 Label:并查集Turbo
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。