POJ 1182 食物链——并查集

POJ 1182 食物链——并查集

挑战程序设计88页原题

#include #include #include #include using namespace std;const int maxn = 150000 + 10;int par[maxn], ran[maxn];void init(int n) { for (int i = 0; i <= n; i++) { par[i] = i, ran[i] = 0; }}int seek(int x) { if (par[x] == x) return x; else return par[x] = seek(par[x]);}void unite(int x, int y) { x = seek(x), y = seek(y); if (x == y) return; if (ran[x] == ran[y]) par[x] = y; else { par[y] = x; if (ran[x] == ran[y]) ran[x]++; }}bool same(int x, int y) { if (seek(x) == seek(y)) return true; else return false;}int N, K;int T[maxn], X[maxn], Y[maxn];void solve() { init(N * 3); int ans = 0; for (int i = 0; i < K; i++) { int t = T[i]; int x = X[i] - 1, y = Y[i] - 1; if (x < 0 || N <= x || y < 0 || N <= y) { ans++; continue; } if (t == 1) { if (same(x, y + N) || same(x, y + 2 * N)) { ans++; } else { unite(x, y); unite(x + N, y + N); unite(x + 2 * N, y + 2 * N); } } else { if (same(x, y) || same(x, y + 2 * N)) { ans++; } else { unite(x, y + N); unite(x + N, y + 2 * N); unite(x + 2 * N, y); } } } printf("%d\n", ans);}int main(){ scanf("%d %d", &N, &K); for (int i = 0; i < K; i++) { scanf("%d %d %d", &T[i], &X[i], &Y[i]); } solve(); return 0;}

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