HDU 1530 Maximum Clique 图论最大团问题

/*
HDU 1530 图论最大团问题 
最大团问题：团（clique）是图论中的用语。对于给定图G=(V,E)。
其中，V={1,…,n}是图G的顶点集，E是图G的边集。
图G的团就是一个两两之间有边的顶点集合。
如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，
则称该团为图G的极大团（maximal clique）。
顶点最多的极大团，称之为图G的最大团（maximum clique）。
最大团问题的目标就是要找到给定图的最大团。
*/
#include
#include
using namespace std;
#define N 60
int n,ans;
int map[N][N],set[N];//set集合用以保存加入的点 

//判断新点是否与原set集合里的点互相连通
bool isClique(int end,int point)
{
  for(int i=1;i  {
    if(!map[set[i]][point])
      return false;
  }
  return true;
}

void dfs(int depth,int point)
{
  //这个深度，即使后面全加入，还是比当前小，不搜了 
  if(depth+(n-point+1)    return ;
  //从一个点开始，递归深搜，
  //如果该点与前面集合中的点相邻，点加入集合，继续搜下一个点
  //如果该点不与前面集合中的点相邻，i++，搜下一个点，直到搜完所有点 
  for(int i=point;i  {
    if(isClique(depth+1,i))
    {
      set[depth+1]=i;
      dfs(depth+1,i+1);
    }
  }
  //搜完所有点，更新最大值 
  if(depth>ans)
    ans=depth;
}

int main()
{
  int i,j;
  while(scanf("%d",&n),n)
  {
    for(i=1;i      for(j=1;j        scanf("%d",&map[i][j]);
    ans=0;
    dfs(0,1);
    printf("%dn",ans);
  }
  return 0;
}