HDU ACM 1530 Maximum Clique->最大團
來源：程序員人生 發(fā)布時間：2015-05-11 09:00:29 閱讀次數(shù)：2631次
分析：最大團的模版題,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); //遞歸搜索后序節(jié)點
}
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;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習有所幫助,可以手機掃描二維碼進行捐贈
