扩展并查集——POJ - 1182

桃扇骨 2021-11-22 09:28 260阅读 0赞

**题目含义**

找出与之前的话不符的假话的数目

**题目分析**

简单的扩展并查集

**题目代码**

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    typedef long long LL;
    const int maxn=5e4+7;
    int f[maxn*3];
    int n,k,d,x,y;
    int get(int x){
        if(f[x]==x)return x;
        else return f[x]=get(f[x]);
    }
    int main(){
        scanf("%d%d",&n,&k);
        int ans=0;
        for(int i=1;i<=n;i++)
            f[i]=i;
        for(int i=0;i<k;i++){
            scanf("%d%d%d",&d,&x,&y);
            if(x>n||y>n){
                ans++;
                continue;
            }
            int fx_sel=get(x),fx_eat=get(x+n),fx_ene=get(x+n+n);
            int fy_sel=get(y),fy_eat=get(y+n),fy_ene=get(y+n+n);
            if(d==1){
                if(fx_sel==fy_eat||fx_sel==fy_ene){
                    ans++;
                    continue;
                }
                f[fy_sel]=fx_sel;
                f[fy_eat]=fx_eat;
                f[fy_ene]=fx_ene;
            }
            else if(d==2){
                if(fx_sel==fy_sel||fx_sel==fy_eat||x==y){
                    ans++;
                    continue;
                }
                f[fy_sel]=fx_eat;
                f[fy_ene]=fx_sel;
                f[fy_eat]=fx_ene;
            }
        }
        printf("%d\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/helman/p/11233921.html

发表评论取消回复

表情：

评论列表（有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ并查集题目汇总

转来的：[http://hi.baidu.com/czyuan\_acm/blog/item/531c07afdc7d6fc57cd92ab1.html][http_hi.ba

墨蓝/ 2022年09月30日 00:44/ 0 赞/ 149 阅读

相关 poj 1182-食物链【并查集】

食物链 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

r囧r小猫/ 2022年08月21日 06:51/ 0 赞/ 164 阅读

相关 poj 1182 食物链 //带权并查集

<pre name="code" class="cpp">include <stdio.h> int ani[55000], rel[55000];

太过爱你忘了你带给我的痛/ 2022年08月14日 02:58/ 0 赞/ 165 阅读

相关并查集（2）--POJ 1182 食物链

食物链 [http://acm.pku.edu.cn/JudgeOnline/problem?id=1182][http_acm.pku.edu.cn_JudgeOnline

拼搏现实的明天。/ 2022年07月15日 08:30/ 0 赞/ 186 阅读

相关 POJ 1182 食物链（并查集+集合有条件合并）

食物链 Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是

曾经终败给现在/ 2022年06月13日 14:40/ 0 赞/ 194 阅读

相关 POJ-1182.食物链(并查集)

[1182.食物链][1182.] Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有

蔚落/ 2022年03月07日 01:36/ 0 赞/ 232 阅读

相关 POJ 1182食物链————并查集复习

[食物链][Link 1] Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 105782 Acc

ゝ一世哀愁。/ 2021年12月03日 12:09/ 0 赞/ 239 阅读

相关 POJ2524 并查集

include<iostream> using namespace std; int father[50005]; int rank[50005

曾经终败给现在/ 2021年11月29日 17:32/ 0 赞/ 296 阅读

相关扩展并查集——POJ - 1182

题目含义找出与之前的话不符的假话的数目题目分析简单的扩展并查集题目代码 include<iostream> include<stdio.h>

桃扇骨/ 2021年11月22日 09:28/ 0 赞/ 261 阅读

相关 poj-1182-食物链【带权并查集】题解

目录 1.题目 2.题意 3.思路 4.代码 1.题目动物

布满荆棘的人生/ 2021年08月30日 00:07/ 0 赞/ 402 阅读