1491. 圆桌座位 Java版

import java.util.*;
public class Main {
    static int n,m;
    // 以下使用的编号为 1-n
    static ArrayList[] friend = new ArrayList[15];//存储这个人的朋友
    static boolean [] use = new boolean[15];//记录该人是否使用
    static int [] sit = new int [15];//存储位置上人的编号
    static int cnt = 0;//记录结果

    //lev指当前第几个位置
    public static void dfs(int lev) {
        //位置坐满了
        if(lev > n) {
            cnt++;return;
        }else if(lev==1) {
            sit = new int [15];
        }

        for(int i = 1;i <= n;i++) {
            if(!use[i]) {
                int lef = sit[lev-1];//第一个位置左边没人
                int rig = sit[(lev+1)%n];//只有最后一个位置右边才有人
                if(!friend[i].contains(lef)&&!friend[i].contains(rig)) {
                    use[i] = true;sit[lev] = i;
                    dfs(lev+1);
                    use[i] = false;sit[lev] = 0;//回溯
                }
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0;i < 15;i++) {
            friend[i] = new ArrayList<Integer>();
        }

        for(int i = 0;i < m;i++) {
            int f1 = sc.nextInt();
            int f2 = sc.nextInt();
            friend[f1].add(f2);
            friend[f2].add(f1);
        }
//      for(int i = 1;i <= n;i++)
//          System.out.println(i+":"+friend[i].toString());
        dfs(1);
        System.out.println(cnt/n);
    }
}