POJ 1182 食物链
点击这里 查看题目
我感觉我学过的并查集一下子看不懂了。总之不是简单的并查集，而是种...种类并查集？简单来说就是基本的并查集只需要判断两个是否属于同一组，而种类并查集则需要判断两个个体之间的关系(同一组？你吃我？我吃你？)
推荐一个题目详解博客：Click HERE
解题思路：
总之我写题解也是为了给自己以后好复习，这里让我茅塞顿开的一些提示：
- 两个个体x和y，如果 par[x] = par[y]，则他们是属于一个组的。(基本并查集概念)，相同的，par[x+N] = par[y+N]，par[x+2*N] = par[y+2*N]。
- 两个个体x和y，如果 par[x] = par[y+N]，表示 x 吃 y 。相同地，par[x+N] = par[y+2*N]，par[x+2*N] = par[y]也表示前者吃后者.
- 两个个体x和y，如果 par[x] = par[y+2*N]，表示 x 被 y 吃。
- 题目隐藏条件：x吃y y吃z z吃x 形成一个条食物链。
x吃y，y吃z。为什么可以传递出z吃x?
x吃y ；par[x] = par[y+N] & par[x+N] = par[y+2*N] & par[x+2*N] = par[y]
y吃z ；par[y] = par[z+N] & par[y+N] = par[z+2*N] & par[y+2*N] = par[z]
故：par[x] = par[y+N] = par[z+2*N]；即z吃x；
代码参考自：Click HERE
#include <iostream>
#include <cstdio>
#define MAX_N 500000
using namespace std;
int N, K, ans = 0;
int par[MAX_N];void init(){for(int i = 0; i < N*3; i++)par[i] = i;
}int find(int x){if(par[x] == x)return x;else return par[x] = find(par[x]); //路径压缩
} void unite(int x, int y){int px = find(x);int py = find(y);if(px != py)par[px] = py;
}int main(){scanf("%d%d", &N, &K);init();for(int i = 0; i < K; i++){int type, x, y;scanf("%d%d%d", &type, &x, &y);x -= 1, y -= 1;if(x < 0 || x >= N || y >= N || y < 0){ans++;continue;} if(type == 1)//同类 {if(find(x) == find(y+N) || find(x) == find(y+2*N)){ans++;continue;} else{unite(x, y);unite(x+N, y+N);unite(x+2*N, y+2*N); } }if(type == 2)//捕食 {if(x == y || find(x) == find(y) || find(x) == find(y+2*N)){ans++;continue;} else{unite(x, y+N);unite(x+N, y+2*N);unite(x+2*N, y);}}}printf("%d\n", ans); return 0;
} POJ 2492 臭虫也疯狂
点击这里 查看题目
我感觉每次两题 第二题都比第一题要简单 whatever 正好拿来增加勇气练手 其实第一题写过之后这题就很简单了 上题有三种关系 这里只有两种关系 所以2*N is appreciated.
校OJ能过 真滴自闭了 不知道为啥在POJ总WA 算辽
这个博客说的很详细了
代码参考
POJ 1703 各...各种姿势？
点击这里 查看题目
I promise this is the last one.
有一种不是用2*N这样的方法写的，用的rank来判断两个群之间的关系。
第二种解法