最大团问题JAVA代码

最大团问题是一个NP完全问题，没有多项式时间算法，只能用指数时间的算法来解决。以下是一个暴力枚举的Java代码：

import java.util.*;

public class MaxClique {
    static int n, max;
    static boolean[][] graph;
    static boolean[] used;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        graph = new boolean[n][n];
        used = new boolean[n];

        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u][v] = graph[v][u] = true;
        }

        max = 1; // 任何一个单独的点都是一个团，所以最大团大小至少为1
        for (int i = 0; i < n; i++) {
            used[i] = true;
            dfs(i, 1);
            used[i] = false;
        }

        System.out.println(max);
    }

    static void dfs(int v, int cnt) {
        if (cnt > max) max = cnt; // 更新最大团大小
        for (int i = v + 1; i < n; i++) {
            if (!used[i] && isClique(v, i)) { // 如果将i加入当前团后仍然是团，就继续搜索
                used[i] = true;
                dfs(i, cnt + 1);
                used[i] = false;
            }
        }
    }

    static boolean isClique(int u, int v) {
        for (int i = 0; i < n; i++) {
            if (i != u && i != v && used[i]) {
                if (!graph[u][i] || !graph[v][i]) {
                    return false;
                }
            }
        }
        return true;
    }
}

输入格式为：

n m
u1 v1
u2 v2
...

其中n为点数，m为边数，ui和vi表示一条无向边。输出为最大团的大小。