[luoguP1196] 银河英雄传说（并查集）

传送门

记录 up[x] 表示 x 上方有多少个

　　 all[x] 表示当前连通的有多少个

find 的时候 和 合并的时候 更新一下即可

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define N 30001 4 #define abs(x) ((x) < 0 ? (x) : (x)) 5 6 int T; 7 int f[N], up[N], all[N]; 8 9 inline int read() 10 17 18 inline int find(int x) 19 26 return f[x]; 27 } 28 29 int main() 30 48 else fx ^ fy ? puts("1") : printf("%d\n", abs(up[x] up[y]) 1); 49 } 50 return 0; 51 }
View Code

上一篇：[luoguP1134] 阶乘问题（数论）

下一篇：差分约束系统总结（转）

---

并查集