最大团.cpp

数值分析中常用的几种算法的实现

#include<stdio.h>
#include<string.h>
int map[51][51];
int max,n,c[51],found;
void clique(int used[],int size,int sum){
	int left[51],i,j,now;
	if(size+sum<=max)
		return;
	memset(left,0,sizeof(left));
	if(sum==0){
		if(size>max){
			max=size;
			found=1;
		}
		return;
	}
	now=0;
	for(i=0;i<n;i++){
		if(used[i]==0)
			continue;
		memset(left,0,sizeof(left));
		if(size+c[i]<=max)
			return;
		left[i]=0;
		now=0;
		for(j=i+1;j<n;j++){
			if(used[j]&&map[i][j]){
				left[j]=1;
				now++;
			}
		}
		if(found==1)
			return;
		clique(left,size+1,now);
	}
	clique(left,size+1,now);
	return;
}
int main(){
	int i,j,left[51],sum;
	freopen("test1.txt","r",stdin);
	while(1){
		scanf("%d",&n);
		max=0;
		memset(c,0,sizeof(c));
		if(n==0)
			return 0;
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				scanf("%d",&map[i][j]);
			}
		}
		for(i=n-1;i>=0;i--){
			found=0;
			sum=0;
			memset(left,0,sizeof(left));
			for(j=i+1;j<n;j++){
				if(map[i][j]){
					left[j]=1;
					sum++;
				}
			}
			clique(left,1,sum);
			c[i]=max;
		}
		printf("%d\n",max);
	}	
}