poj1182 拆点并查集

poj1182

题意:中文题

思路:去年做的带权并查集,拆点的姿势还是要学习一个的

AC代码:

#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a) memset(a,0,sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
using namespace std;
const long long INF = 1e18+1LL;
const int inf = 1e9+1e8;
const int N=1e5+100;
const ll mod=1e9+7;

int n,k,ans,pre[N<<1];
void init(int n){
    for(int i=0; i<=3*n; ++i) pre[i]=i;
}
int finds(int x){
    return pre[x]=pre[x]==x?x:finds(pre[x]);
}
void unions(int x, int y){
    int fx=finds(x), fy=finds(y);
    pre[fy]=fx;
}
int main(){
    //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    init(n);
    for(int i=1; i<=k; ++i){
        int d,x,y;
        scanf("%d%d%d",&d,&x,&y);
        if(x>n || x<1 || y>n || y<1){
            ans++;
            continue;
        }
        if(d==1){
            if(finds(x)==finds(y+n) || finds(x)==finds(y+2*n)){
                ans++;
            }
            else{
                unions(x,y);
                unions(x+n,y+n);
                unions(x+2*n,y+2*n);
            }
        }
        else{
            if(finds(x)==finds(y) || finds(x)==finds(y+2*n)){
                ans++;
            }
            else{
                unions(x,y+n);
                unions(x+n,y+2*n);
                unions(x+2*n,y);
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}
时间: 07-20

poj1182 拆点并查集的相关文章

POJ1182 食物链 【并查集变种】

挺简单的 N个元素扩展为 3*N个 i-A i-B i-C A吃B吃C吃A 挑战程序设计的89面 #include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <cmath> using namespace std; int N,K; const int MAX_N=333333; //并查集 int par[MAX_N]; int ran

POJ-1182食物链(并查集的运用)

Description 动物王国中有三类动物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句话有的是真的,有的是假的.当一句话满足下列三条之

并查集&amp;MST

[HDU] 1198 Farm Irrigation 基础最小生成树★ 1598 find the most comfortable road 枚举+最小生成树★★ 1811 Rank of Tetris 并查集+拓扑排序★★ 3926 Hand in Hand 同构图★ 3938 Portal 离线+并查集★★ 2489     Minimal Ratio Tree dfs枚举组合情况+最小生成树★ 4081     Qin Shi Huang's National Road System 最

POJ1182 食物链---(经典种类并查集)

题目链接:http://poj.org/problem?id=1182 食物链 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 69207   Accepted: 20462 Description 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形.A吃B, B吃C,C吃A. 现有N个动物,以1-N编号.每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种. 有人用两种说法对这N个动物所构成的食

POJ 1182 食物链(并查集拆点)

[题目链接] http://poj.org/problem?id=1182 [题目大意] 草原上有三种物种,分别为A,B,C A吃B,B吃C,C吃A. 1 x y表示x和y是同类,2 x y表示x吃y 问给出的信息有几条是和前面相违背的 [题解] 之前这道题是用加权并查集做的,做的有些晕晕乎乎,现在换了种思路做就清晰很多了 将每个点拆点,比如x拆为,x-A,x-B,x-C 表示x属于A类,x属于B类,和x属于C类, 如果y和x属于同类,那么合并x-A和y-A,x-B和y-B,x-C和y-C 如果

【POJ1182】 食物链 (带权并查集)

Description 动物王国中有三类动物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句话有的是真的,有的是假的.当一句话满足下列三条之

(POJ1182)食物链(带权并查集-附通用模板)

食物链 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 74914   Accepted: 22257 Description 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形.A吃B, B吃C,C吃A. 现有N个动物,以1-N编号.每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种. 有人用两种说法对这N个动物所构成的食物链关系进行描述: 第一种说法是"1 X Y",表示X和Y是同

【并查集&amp;&amp;带权并查集】BZOJ3296&amp;&amp;POJ1182

bzoj1529[POI2005]ska Piggy banks [题目大意] n头奶牛m种语言,每种奶牛分别掌握一些语言.问至少再让奶牛多学多少种语言,才能使得它们能够直接或间接交流? [思路] (n+m)个点,奶牛学会某种语言就合并它和语言的节点.并查集维护联通块,答案为联通块个数-1.水,可是我跳坑了. 我一开始做法是设总的联通块有(n+m)个,然后没合并一次减去1.其实这样是不可行的,因为我们只需要考虑奶牛(即节点1..n)有几个联通块.有可能一些语言根本没有任何奶牛掌握-- 1 #in

带权并查集 poj1182

首先要注意核心代码 int find(int i){    if(i == fa[i])        return fa[i];    int tt = find(fa[i]);    num[i] = (num[i] + num[fa[i]]) % 3;    fa[i] = tt;    return fa[i];}不能写成 int find(int i){    if(i == fa[i])        return fa[i];    fa[i] = find(fa[i]);