poj1182-食物链-带权并查集-种类并查集

Cwolf9 2018-04-13 原文

（这应该是我写的第一个和带权并查集相关的题，还不是很了解，所以这篇博客我以后还会做修改，力求更号理解！

题意和思路：

中文题意，我简单提一下：

A->B,B->C,C->A。A吃B，B吃C，C吃A，这是循环的。

r[] 数组保存的是该节点和祖先节点的关系：

0-和祖宗节点同类；

1-吃祖宗节点；

2-被祖宗节点吃。

输入：

scanf(“%d%d%d”,&c,&a,&b);

if(c==1) a和b节点同类；

if(c==2) a吃b。

注意：c-1就和最上面数字的数字表示相同的意思。

输出: 假语句的数量

题目链接：

　　点击做题

代码：

把多组输入去掉就能AC，md，poj多组输入这个坑好烦啊啊啊啊！！！

/* 
*/  
//#include<bits/stdc++.h>   
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<map>  
#include<queue>  
#include<set>  
#include<string>  
#include<cmath>  
#define test printf("***\n")  
#define mm1(a) memset((a),-1,sizeof((a)))    
#define mm0(a) memset((a),0,sizeof((a)))    
#define mmx(a) memset((a),0x3f,sizeof((a)))    
#define ka getchar();getchar()  
#define ka1 getchar()  
#define lowbit(x) (x)&(-(x))  
#define iis std::ios::sync_with_stdio(false)  
using namespace std;  
typedef long long LL;  
typedef unsigned long long uLL;  
const int N = 50005;  
const int M = 4100005;  
const int X = 999983;  
const int INF = 1e9;  
const double eps = 1e-8;  
const int mod = 1e9 + 7;  

int n,m;  
int fa[N];  
int r[N];  
int Fi(int x){  
    if(x!=fa[x]){  
        int t=fa[x];  
        fa[x]=Fi(fa[x]);  
        r[x]=(r[x]+r[t])%3;  
    }  
    return fa[x];  
}  
void un(int a,int b,int c){  
    int pa=Fi(a),pb=Fi(b);  
    fa[pb]=pa;  
    r[pb]=(r[a]+c-1-r[b]+3)%3;  
    Fi(a),Fi(b);  
}  
int main(){  
#ifdef DEBUG  
    freopen("D:in.in", "r", stdin);  
    freopen("D:out.out", "w", stdout);    
#endif  
    while(~scanf("%d%d",&n,&m)){  
        mm0(r);  
        for(int i=0;i<=n;++i)fa[i]=i;  
        int ans=0,a,b,c;  
        for(int h=0;h<m;++h){  
            scanf("%d%d%d",&c,&a,&b);  
            if(a>n||b>n||(c==2&&a==b)){  
                ans++;continue;  
            }  
            int pa=Fi(a),pb=Fi(b);  
            if(pa!=pb){  
                un(a,b,c);  
            }else{  
                if(r[b]!=(r[a]+c-1)%3)ans++;  
            }  
        }  
        printf("%d\n",ans );  
    }  
#ifdef DEBUG  
    fclose(stdout);  
    fclose(stdin);  
#endif  
    return 0;  
}