# [POJ 1182] 食物链【并查集】

• 2018-01-04
• 0
• 0

## Problem:

 Time Limit: 1000MS Memory Limit: 10000K

Description

1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。

Input

Output

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`

Source

Noi 01

## Solution:

## 又一句题外话，昨天刚说 POJ 上难得见到中文题，结果立马又来了一道。。##

• O(N+Kα(K))，其中 α() 为反 Ackerman 函数，对于任意“可以想象”的正整数 x，总有 α(x) ≤ 4。

## Code: O(N+Kα(K)) [556K, 250MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N, K, ans = 0;
int fa[50005], anc;
int rel[50005];  // Record the relation between i and fa[i]

inline void ds_init() {for(register int i = 1; i <= N; i++) fa[i] = i;}

inline int ds_find(int u){
if(fa[u] == u) return u;
anc = ds_find(fa[u]);  // Find ancestor
rel[u] = (rel[u] + rel[fa[u]]) % 3;
return fa[u] = anc;
}

inline bool ds_union(int u, int v, int relat){
int ancu = ds_find(u), ancv = ds_find(v);
if(ancu == ancv) return rel[v] == (rel[u] + relat) % 3;  // Former statements have mentioned
else{
fa[ancv] = ancu;
rel[ancv] = (rel[u] - rel[v] + relat + 3) % 3;
// Infer this formula for a purpose of setting (rel[u] + relat) % 3 == rel[v]
return true;  // Never mentioned before
}
}

int main(){
scanf("%d%d", &N, &K);
ds_init();
for(register int i = 1; i <= K; i++){
int D, X, Y;
scanf("%d%d%d", &D, &X, &Y);
if(X < 1 || X > N || Y < 1 || Y > N) {ans++; continue;}
if(!ds_union(X, Y, --D)) ans++;
}
printf("%d\n", ans);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai