atcoder ABC310 D - Peaceful Teamsの勉強

DFS,BFS atcoder

atcoder.jp

・参考：
AtCoder ABC 310 D - Peaceful Teams (水色, 400 点) - けんちょんの競プロ精進記録

・やったこと：参考記事をpythonで実装した。dfsで全探索することを使う(参考、
よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの競プロ精進記録)。

n,t,m=map(int,input().split())
ng=[[1 for _ in range(n+1)]for _ in range(n+1)]  #仲が悪い組を管理するリスト。
#print(ng[0][0])

for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  ng[a][b]=ng[b][a]=0   #仲が悪い組は0に
  
def dfs(groups,i): #groupsが各々のグループ(g)を含む。
  #終端条件。i=n-1の最後の点まで見たいので。
  if i==n:
    #グループをt個にわけれたら1を返す
    if len(groups)==t:
      return 1
    else:
      return 0
    
  ans=0  #組分けの数。
  
  #iを新しいグループ(g)に。g=[i]
  groups.append([i])
  ans+=dfs(groups,i+1)   #グループをわけれたら+1していく
  groups.pop()
  
  #iをすでにあるグループ(g)にいれる事ができるか。
  for g in groups:
    #gの中でiと仲が悪い人がいるときスルー
    flag=0
    for v in g:
      if ng[v][i]==0:
        flag=1
    if flag:  
      continue
  
    #iをgに入れる
    g.append(i)
    ans+=dfs(groups,i+1)
    g.pop()
    
  return ans

groups=[]
print(dfs(groups,0))