最大团问题

最大团展开目录

给定无向图 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;
    }
}