考え方
Editorial - freee Programming Contest 2023（AtCoder Beginner Contest 310）アライグマ「D問題はDFSの練習問題なのだ！ 1番目の選手から順に、何番目のチームにいれるかDFSで決めて、最後にチーム数をチェックすればいいのだ」 pic.twitter.com/JJKZqUXp3u
— 競技プログラミングをするフレンズ (@kyopro_friends) July 15, 2023
回答例
PyPy3 (7.3.0)だと間に合う．Python (3.8.2)だとTLE．from copy import deepcopy N, T, M = map(int, input().split()) G = [set() for _ in range(N)] for _ in range(M): a, b = map(int, input().split()) a -= 1 b -= 1 G[a].add(b) G[b].add(a) def f(i, team): global ans if i == N - 1: if len(team) == T: ans += 1 return for j in range(len(team)): if team[j] & G[i + 1]:continue tmp = deepcopy(team) tmp[j].add(i+1) f(i + 1, tmp) if len(team) < T: f(i + 1, team + [set([i + 1])]) ans = 0 f(0, [set([0])]) print(ans)
