HDU ACM 1530 Maximum Clique->最大团
来源：程序员人生 发布时间：2015-05-11 09:00:29 阅读次数：2454次
分析：最大团的模版题,DFS深搜。
#include<iostream>
using namespace std;
#define N 55
int map[N][N];
int set[N];
int max;
bool IsConnect(int end,int v)
{
int i;
for(i=0;i<end;i++)
if(!map[set[i]][v])
return false;
return true;
}
void DFS(int depth,int u,int n)
{
int i;
if(depth+(n-(u⑴))<=max) //剪枝，后面不比前面的大则不用找了
return ;
for(i=u;i<=n;i++)
if(IsConnect(depth,i))
{
set[depth]=i;
DFS(depth+1,i+1,n); //递归搜索后序节点
}
if(depth>max) //更新最大值
max=depth;
}
int main()
{
int n,i,j;
while(scanf("%d",&n)==1 && n)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&map[i][j]);
max=0;
DFS(0,1,n); //从第0层第1个顶点开始搜
printf("%d
",max);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
