最大团问题

最大团

给定无向图G=(V,E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是定点的无序对，无序对常用圆括号“()”表示。

普及几个概念：

• 无向图：边没有方向。如果点A和B之间有一条边，那么既可以从A到B，也可以从B到A
• 完全图：任意两点之间都有边相连。假设一个图有$n$个点，那么就应该有$\frac{n\times(n-1)}{2}$条边
• 子图：选取原图中的部分结点，以及与该点相连的所有边，构建出的新图

了解上面几个概念以后，给出最大团的定义：在一个无向图中找出一个点数最多的完全子图

DFS求最大团

假设现在有这么一个图，我们用肉眼看一下就知道他的最大团数是3，(1,2,5)，(1,4,5)，(2,3,5)都是最大团

DFS求最大团的主要思路是构建一棵二叉子集树，每次枚举添加或不添加当前结点到当前已经构建好的团中，如下图，0就是不添加，1就是添加

这样枚举的话时间复杂度是$O(2^n)$，考虑能不能剪枝，答案当然是可以的

首先思考一下，什么情况下，枚举到的这个结点可以选？假设DFS执行下来我已经选了1和2，那么3选还是不选？肯定不选，因为如果选了就无法与1和2构成完全图

假设我在搜索过程中已经得到了一个解bestn，如果剩下的所有点加上我当前已选的点，都不够超过bestn，那我就没必要往后枚举了。这个说起来可能比较抽象，举个例子，一共5个点，bestn已经更新成了3，当前树的路径是{1,0}（对应的选择就是1选，2不选），假设现在枚举3不选，那么还剩下两个点4,5，不管4,5能不能与我当前的团构成完全图，我就假设4，5都选上，那么我最大团的结点数为3，根本没有超过bestn，都无法得到更好的答案，我干嘛要枚举呢，所以3不选的这棵子树直接砍了

代码

import java.util.Scanner;

public class Main {
    static int[][] map;//邻接矩阵保存图
    static int[] book;//记录每个点选还是不选
    static int bestn = Integer.MIN_VALUE;
    static int n,m;//n个点，m条边
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        m = cin.nextInt();
        map = new int[n + 1][n + 1];
        book = new int[n + 1];
        for(int i = 0;i < m;i++) {
            int a = cin.nextInt();
            int b = cin.nextInt();
            map[a][b] = 1;
            map[b][a] = 1;
        }
        dfs(1,0);
        System.out.println(bestn);
    }
    static void dfs(int idx,int num) {//第idx个点，当前选了num个点
        if(idx == n + 1) {
            bestn = Math.max(bestn,num);
            return;
        }
        for(int i = 0;i < 2;i++) {//二叉树
            if(i == 0) {//不选
                if(num + n - idx > bestn) 
                    dfs(idx + 1,num);
            } else { //选
                if(check(idx)) {
                    book[idx] = 1;
                    dfs(idx + 1,num + 1);
                    book[idx] = 0;
                }
            }
        }
    }
    static boolean check(int idx) {
        for(int i = 1;i < idx;i++) 
            if(book[i] == 1 && map[i][idx] != 1)
                return false;
        return true;
    }
}
/*
输入：
5 7
1 2
2 3
5 3
4 5
1 4
1 5
2 5
输出：
3
*/

HDU1530

题意：给定N个点的无向图，让你求最大团
Java tle了，不知道为什么

import java.util.Scanner;

public class Main {
    static int[][] map;
    static int[] book;
    static int bestn;
    static int n;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (true) {
            bestn = Integer.MIN_VALUE;
            n = cin.nextInt();
            if(n == 0)
                break;
            map = new int[n + 1][n + 1];
            book = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    int flag = cin.nextInt();
                    map[i][j] = flag;
                }
            }
            dfs(1, 0);
            System.out.println(bestn);
        }
    }

    static void dfs(int idx, int num) {
        if (idx == n + 1) {
            bestn = Math.max(bestn, num);
            return;
        }
        for (int i = 0; i < 2; i++) {
            if (i == 0) {
                if (num + n - idx > bestn)
                    dfs(idx + 1, num);
            } else { 
                if (check(idx)) {
                    book[idx] = 1;
                    dfs(idx + 1, num + 1);
                    book[idx] = 0;
                }
            }
        }
    }

    static boolean check(int idx) {
        for (int i = 1; i < idx; i++)
            if (book[i] == 1 && map[i][idx] != 1)
                return false;
        return true;
    }
}