maximum clique(最大团).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>

#define NMAX 51

bool path[NMAX][NMAX];
int n, mmax;
int dp[NMAX];
bool v[NMAX];

bool dfs(int pos, int size) 
{
	int i, j, unvis;
	bool tv[NMAX];
	
	unvis = 0;
	for (i=pos;i<n;i++) {
		if (!v[i]) {
			unvis ++;
		}
	}
	if (unvis == 0) {//|U| = 0
		if (size > mmax) {
			mmax = size;
			return true;
		}
		return false;
	}

	for (i=pos; i < n && unvis > 0 ;i++) {
		if (!v[i]) {
			if (unvis + size <= mmax || dp[i] + size <= mmax) {
				return false;
			}
			v[i] = true;//U = U\{vi}
			unvis --;
			memcpy(tv, v, sizeof(v));
			for (j=0;j<n;j++) {//U ∩ N(vi);
				if (!path[i][j]) {
					v[j] = true;
				}
			}
			if ( dfs(i, size+1) ) {
				return true;
			}
			memcpy(v, tv, sizeof(v));
		}
	}//while U is not empty
	return false;
}


int max_clique()
{
	int i,j;
	mmax = 0;
	
	for (i=0;i<n;i++) {
		path[i][i] = false;
	}
	for (i=n-1;i>=0;i--) {
		for (j=0;j<n;j++) {//Si ∩ N(vi);
			v[j] = !path[i][j];
		}
		dfs(i, 1);
		dp[i] = mmax;
	}
	return mmax;
}

int main()
{
	int i,j;
	while (scanf("%d", &n), n) {
		for (i=0;i<n;i++) {
			for (j=0;j<n;j++) {
				scanf("%d", &path[i][j]);
			}
			dp[i] = 0;
		}
		printf("%d\n", max_clique());
	}
}