阐述

标准bfs
对象——n个朋友 规则——拒绝朋友

两个关键点
1. 要提前确定一个朋友的位置，保证不会因角度不同产生多个解
2. 字典的初始化要完全，没有朋友的也要初始化，不然KeyError

推荐2 二者时间相差1倍

代码1

#边搜边查
def dfs(pos):
    global count
    if pos == N:  #超一个
        # 检查首尾是否是朋友
        if path[N-1] not in friends[path[0]]:
            count += 1
        return
    for num in range(2, N+1):
        if not visited[num]:
            # 检查当前数字与前一个数字是否是朋友
            if num not in friends[path[pos-1]]:
                path[pos] = num
                visited[num] = True
                dfs(pos + 1)
                visited[num] = False

N, M = map(int, input().split())
friends = {i: set() for i in range(1, N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    friends[a].add(b)
    friends[b].add(a)

count = 0
visited = [False] * (N + 1)
path = [0] * N
path[0] = 1  # 固定人1在第一个位置，很关键
visited[1] = True
dfs(1)
print(count)

代码2

#全排列后检查
def check():
    for i in range(n):
        now=path[i]
        if i==0:
            last=path[n-1]
        else:
            last=path[i-1]
        if now in good[last]:   #注意，要初始化全部字典，不然KeyError
            return False
    return True

def dfs(depth):
    global ans
    if depth==n and check():
        ans+=1
        #print(path)

    for i in range(2,n+1):
        if vis[i]==False:
            path[depth]=i
            vis[i]=True    
            dfs(depth+1)
            vis[i]=False

n,m=map(int,input().split())
good={i:set() for i in range(n+1)}
for i in range(m):
    a,b=map(int,input().split())
    if a not in good:
        good[a]=set()
    if b not in good:
        good[b]=set()
    good[a].add(b)
    good[b].add(a)
#print(good)
ans=0
vis=[False]*(n+2)
path=[0]*(n+2)
path[0]=1
dfs(1)
print(ans)