2279.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2279 on 2006-06-23 at 00:46:48 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 128, S = 4;
const int LMT = 1000, LN = 1024;

class Set {
public:
	int e[S];
	bool eq;
	Set() : eq(false) { clear(); }
	void clear() { memset(e, 0, sizeof(e)); }
	Set set(int idx) { e[idx>>5] |= 1<<(idx&31); return *this; };
	bool ctn(const Set&) const;
	Set ins(const Set&) const;
	bool operator ==(const Set&) const;
	bool operator <(const Set&) const;
};
bool Set::ctn(const Set& s) const {
	int i;
	for(i = 0; i < S; i++)
		if((e[i]&s.e[i]) != s.e[i]) return false;
	return true;
}
Set Set::ins(const Set& s) const {
	Set r; int i;
	for(i = 0; i < S; i++) r.e[i] = e[i]&s.e[i];
	return r;
}
bool Set::operator ==(const Set& s) const {
	int i;
	for(i = 0; i < S; i++)
		if(e[i] != s.e[i]) return false;
	return true;
}

int main()
{
	Set g[N], s[LN], tmp[LN];
	int n, m, i, j, k;

	while(scanf("%d %d", &n, &m) != EOF) {
		for(i = 0; i < n; i++) g[i].clear();
		for(i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b);
			if(a < b) swap(a, b);
			g[a-1].set(b-1);
		}
		int sn = 1; s[0].clear(); s[0].set(0);
		for(i = 1; i < n && sn <= LMT; i++) {
			int kn = 0;
			bool in[LN] = { false }, e[LN] = { false };
			for(j = 0; j < sn; j++) {
				tmp[kn++] = g[i].ins(s[j]);
				if(tmp[kn-1] == s[j]) { in[j] = true; tmp[kn-1].eq = true; }
			}
			for(j = 0; j < sn; j++)
				if(in[j]) s[j].set(i);
			for(j = 0; j < kn; j++)
				for(k = 0; k < kn; k++)
					if(j != k && !e[j] && tmp[j].ctn(tmp[k])) {
						e[k] = true;
						if(tmp[j] == tmp[k]) tmp[j].eq |= tmp[k].eq;
					}
			for(k = 0; k < kn && sn <= LMT; k++)
				if(!e[k] && !tmp[k].eq) s[sn++] = tmp[k].set(i);
		}
		if(sn > LMT) printf("Too many maximal sets of friends.\n");
		else printf("%d\n", sn);
	}
	
	return 0;
}