#include<stdio.h>
#include<memory.h>
#include<vector>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<memory.h>

using namespace std;

int N,V;
int **g, *dp, **stk, mx;
vector<int> vetexlist;
vector<int> maxcliquelist;

int dfs(int n, int ns, int dep){
	int i, j, k, p, cnt;  
	if (0 == ns) { 
		if (dep > mx)
		{
			mx = dep;
			vector<int>::iterator iter = vetexlist.begin();
			maxcliquelist.clear();
			for(;iter!=vetexlist.end();iter++)
			{
				maxcliquelist.push_back(*iter);
			}
		}
		return 1; 
	}
	for (i = 0; i < ns; i++) { 
		k = stk[dep][i]; 
		cnt = 0; 
		if (dep + n - k <= mx) return 0; 
		if (dep + dp[k] <= mx) return 0; 
		for (j = i + 1; j < ns; j++) { 
			p = stk[dep][j]; 
			if (g[k][p])
			{
				stk[dep + 1][cnt++] = p;
			}
		}
		vetexlist.push_back(k);
		dfs(n, cnt, dep + 1);
	} 
	return 1; 
}

int clique(int n)
{
	int i, j, ns;
	for (mx = 0,  i = n - 1; i >= 0; i--)
	{
		for (ns = 0, j = i + 1; j < n; j++) 
		{
			if (g[i][j])
			{
				stk[1][ ns++ ] = j;
			}
		}
		vetexlist.push_back(i);
		dfs(n, ns, 1);
		vetexlist.clear();
		dp[i] = mx;
	}
	return mx;
}

int main()
{
	//ostringstream ofs;
	scanf("%d",&N);
	int i,j,k,v1,v2;
	int edgeCount;
	for(i=0;i<N;i++)
	{
		scanf("%d%d",&V,&edgeCount);
		g = new int*[V];
		dp = new int[V];
		memset(dp,0,sizeof(int)*V);
		stk = new int*[V];
		for(j=0;j<V;j++)
		{
			g[j] = new int[V];
			stk[j] = new int[V];
			for(k=0;k<V;k++)
			{
				g[j][k] = 1;
			}
		}
		for(j=0;j<edgeCount;j++)
		{
			scanf("%d%d",&v1,&v2);
			g[v1-1][v2-1] = 0;
			g[v2-1][v1-1] = 0;
		}
		cout<<clique(V)<<endl;
		sort(maxcliquelist.begin(),maxcliquelist.end());
		vector<int>::iterator iter = maxcliquelist.begin();
		//ofs<<*iter+1;
		for(;iter!=maxcliquelist.end();iter++)
		{
			cout<<*iter+1<<" ";
		}
		cout<<endl;
	}
	//cout<<ofs.str();
	return 0;
}

• 纠正了，是递归里存在小问题，附上0ms AC代码~ (1971) tbziy2 2011-05-28 10:43:49
• Re:补图最大团有模版，搜索是王道啊，可惜我怎么都不会搜索，伤不起！！！ (0) yuanchuanshun 2012-07-02 17:03:43