POJ 1182 食物链——种类并查集

POJ 1182 食物链——种类并查集

感觉这种题型快忘了，拿出来复习一下。

​

#include #include #include #include using namespace std;const int maxn = 5e4 + 10;struct Node { int fa; int rel;}node[maxn];void init(int n) { for (int i = 1; i <= n; i++) { node[i].fa = i; node[i].rel = 0; }}int query(int x) { if (x == node[x].fa) return x; int y = node[x].fa; node[x].fa = query(y); node[x].rel = (node[y].rel + node[x].rel) % 3; return node[x].fa;}int main() { int n, k; scanf("%d%d", &n, &k); init(n); int d, x, y, ans = 0; while (k--) { scanf("%d%d%d", &d, &x, &y); if (x > n || y > n) ans++; else if (d == 2 && x == y) ans++; else { int rx = query(x), ry = query(y); if (rx == ry) { if ((3 - node[x].rel + node[y].rel) % 3 != d-1) ans++; } else { node[ry].fa = rx; node[ry].rel = (node[x].rel + d - 1 + 3 - node[y].rel) % 3; } } } printf("%d\n", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。