BZOJ 3632: 우주 여행

사 차 오리지널?완전 노출 의 최대 단 문제.
최대 그룹의 학습 자 료 는 이 링크 를 볼 수 있 습 니 다.http://www.cnblogs.com/zhj5chengfeng/archive/2013/07/29/3224092.html

#include<bits/stdc++.h>
using namespace std;
const int maxn=50+10;
int n,ans,f[maxn],flo[maxn][maxn];
bool G[maxn][maxn];
bool DFS(int cur,int res)
{
	if(!cur)
	{
		if(res>ans)
		{
			ans=res;
			return true;
		}
		return false;
	}
	for(int i=0;i<cur;i++)
	{
		if(res+cur-i<=ans)
			return false;
		int u=flo[res][i];
		if(res+f[u]<=ans)
			return false;
		int suf=0;
		for(int j=i+1;j<cur;j++)
			if(G[u][flo[res][j]])
				flo[res+1][suf++]=flo[res][j];
		if(DFS(suf,res+1))
			return true;
	}
	return false;
}
int maxclique()
{
	for(int i=n-1;i>=0;i--)
	{
		int cur=0;
		for(int j=i+1;j<n;j++)
			if(G[i][j])
				flo[1][cur++]=j;
		DFS(cur,1);
		f[i]=ans;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	int u,v;
	while(scanf("%d%d",&u,&v)!=EOF)
		G[u-1][v-1]=G[v-1][u-1]=true;
	printf("%d
",maxclique());
	return 0;
}
/*
4
1 2
2 3
3 1
1 4
*/