//注意是围成一个圆,第一个人和最后一个人也不能是朋友
题目描述
N个人围坐一圈,有 M对朋友关系。
第 i对朋友关系是指,编号是 ai的人和编号是 bi的人是朋友。
现在要给他们安排座位,要求所有相邻的人不能是朋友。
问共有多少种方案?
如果两个方案只有旋转角度不同,则我们将其视为一种方案。
样例
import java.util.*;
public class Main {
static int n;
static int pengyou[][]=new int[11][11];
static long num=0;
static int a[]=new int[12];
public static void main(String[] arg) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int m=sc.nextInt();
int x,y;
for(int i=0;i<m;i++) {
x=sc.nextInt();
y=sc.nextInt();
pengyou[x][y]=1;
pengyou[y][x]=1;
}
boolean falg[]=new boolean[13];
falg[1]=true;
a[1]=1;
dfs(2,n,falg);
System.out.println(num);
}
public static void dfs(int wei,int end,boolean falg[]) {
if(wei>end) {
if(pengyou[1][a[wei-1]]==0) {
num++;
}
return ;
}
for(int i=1;i<=end;i++) {
if(pengyou[i][a[wei-1]]!=1 && !falg[i]) {
falg[i]=true;
a[wei]=i;
dfs(wei+1, end,falg);
a[wei]=0;
falg[i]=false;
}
}
}
}