graph coloring(最大独立集).cpp

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

#include <cstdio>
#include <string>

#define NMAX 110

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

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;
			seq_pos = 0;//record path
			seq[ seq_pos ++] = pos+1;
			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) ) {
				seq[ seq_pos ++] = pos+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,x,y,e;
	int m,tn;
	scanf("%d", &m);
	while (m --) {
		scanf("%d %d", &n, &e);
		memset(path,0,sizeof(path));
		for (i=0;i<e;i++) {
			scanf("%d %d", &x,&y);
			x--;	y--;
			path[x][y] = path[y][x] = true;
		}
		//max independent set in original graph
		//max clique in inverse graph
		for (i=0;i<n;i++) {
			for (j=0;j<n;j++) {
				path[i][j] = !path[i][j];
			}
		}
		memset(dp,0,sizeof(dp));
		printf("%d\n", max_clique());

		printf("%d", seq[0]);
		for (i=1;i<seq_pos;i++) {
			printf(" %d", seq[i]);
		}
		printf("\n");
	}
}