Maximum Clique（HDOJ 1530）

Problem Description

Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex.

Input

Input contains multiple tests. For each test:

The first line has one integer n, the number of vertex. (1 < n <= 50)

The following n lines has n 0 or 1 each, indicating whether an edge exists between i (line number) and j (column number).

A test with n = 0 signals the end of input. This test should not be processed.

Output

One number for each test, the number of vertex in maximum clique.

Sample Input

5
0 1 1 0 1
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
1 1 1 1 0
0

Sample Output

4 

My Code

什么叫团，团就是完全子图，满足任意两点都恰有一条边相连的子图。如果一个团不是其他团的子集，那么这样的团就是极大团，而最大团就是点最多的极大团。最大团问题是一个NPC问题，所以暴力就行了，网上有许多最大团的算法，其实就是用各种方法来给dfs剪枝。比较常用的是 Bron-Kerbosch 算法 ，不过网上很多都讲的不太清楚，可以尝试自己手工模拟一下，有助于理解这个算法。

#include 
#include 
using namespace std;

int n;
int map[55][55];            //存图
int vis[55];                //记录，目前已经取了的点
int cnt[55];                //cnt[i]表示从i到n中最大团的大小
int maxn;                   //最大团的大小
bool dfs(int u, int now)    //now表示当前已选的点的个数
{
    for (int i = u + 1; i <= n; i++)
    {
        if (cnt[i] + now <= maxn)       //剪枝，如果之前的最大团加上现在选的点还是比最优解小，那么就return
            return false;
        if (map[u][i])
        {
            int j;
            for (j = 0; j < now; j++)
                if (!map[i][vis[j]])    //判断i是否和当前团中元素都相邻
                    break;
            if (j == now)
            {
                vis[now] = i;           //是的话，入团
                if (dfs(i, now + 1))    //往下继续选点
                    return true;
            }
        }
    }
    if (now > maxn)         //更新答案，如果要输出最大团中有哪些点的话，在这里存答案，这题没有
    {
        maxn = now;
        return true;        //每存一个点，最大团大小最多加1，所以后面不需要再搜索了
    }
    return false;
}
void maxClique()
{
    maxn = -1;
    for (int i = n; i > 0; i--)     //因为cnt表示i到n中最大团大小，所以要从n开始倒着遍历。
    {
        vis[0] = i;
        dfs(i, 1);
        cnt[i] = maxn;
    }
}
int main()
{
    while (cin >> n && n)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &map[i][j]);
        maxClique();
        printf("%d
", maxn);
    }
    return 0;
}