1371.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1371 on 2005-10-19 at 00:14:28 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
#define  MAX  51200
using namespace std;

typedef pair<long, int> pli;

class UFSet {
public:
	long list[MAX];
	int rank[MAX];
	void makeSet() {
		memset(list, -1, sizeof(list));
		memset(rank, 0, sizeof(rank));
	}
	pli find(long x) {
		if(list[x] == -1) {
			return pli(x, 0);
		} else {
			pli t = find(list[x]);
			list[x] = t.first;
			rank[x] = (rank[x] + t.second) % 3;
			return pli(list[x], rank[x]);
		}
	}
	void unionSet(long x, long y, bool eat) {
		pli pX = find(x);
		pli pY = find(y);
		list[pY.first] = pX.first;
		if(eat) {
			rank[pY.first] = (rank[x]+4-rank[y]) % 3;
		} else {
			rank[pY.first] = (rank[x]+3-rank[y]) % 3;;
		}
	}
};

int main()
{
	UFSet ufs;
	int D;
	long X, Y, N, K;
	long i, lie;
	pli x, y;

	while(scanf("%ld %ld", &N, &K) == 2) {
		ufs.makeSet();
		lie = 0;
		for(i = 0; i < K; i++) {
			scanf("%d %ld %ld", &D, &X, &Y);
			if(X > N || Y > N) {
				lie++;
			} else if(D == 1) {
				x = ufs.find(X);
				y = ufs.find(Y);
				if(x.first != y.first) {
					ufs.unionSet(X, Y, false);
				} else if(x.second != y.second) {
					lie++;
				}
			} else {
				x = ufs.find(X);
				y = ufs.find(Y);
				if(x.first != y.first) {
					ufs.unionSet(X, Y, true);
				} else if((x.second + 1) % 3 != y.second) {
					lie++;
				}
			}
		}
		printf("%ld\n", lie);
	}
	
	return 0;
}