[POJ1703]Find them, Catch them（并查集）

传送门

1.开两个并查集 f[x] 表示 x 的同类 f[x + n] 表示 x 的敌人

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define N 200001 4 5 int T, n, m; 6 int f[N]; 7 8 inline int read() 9 16 17 inline int find(int x) 18 21 22 inline void connect(int x, int y) 23 28 29 int main() 30 50 else 51 55 } 56 } 57 }
View Code

2.带权并查集

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define N 1000001 4 5 int T, n, m; 6 int f[N], d[N]; 7 8 inline int read() 9 16 17 inline int find(int x) 18 25 return f[x]; 26 } 27 28 inline void connect(int x, int y) 29 34 35 int main() 36 57 } 58 } 59 return 0; 60 }
View Code

上一篇：[luoguP2754] 星际转移问题（最大流）

下一篇：[HDU2328]Corporate Identity（后缀数组）

---

并查集