まずは美味しい順にソートして上からK個取る。そこから、残りのN-K個のうちでどれかと交換することで満足度が上がるかどうかを見ていくわけだが、この時、すでに取っているネタの種類がi種類であれば、そこから種類を減らすことによって満足度は決して上がらない。
何故ならば種類は多いほど満足度が上がるし、そもそも最初にK個選んだ時点で美味しい順に取っているので、i未満の種類を選ぶことによって純粋な「美味しさの和」を上昇させることが不可能なためである。
したがって、ここから
１、種類を減らさずに（★逆に言えば、現時点で食べようと思っている寿司の中にないネタを選んで）
２、交換することで満足度が上昇するか
についてを、残りのN-K個の寿司について考える。（N-K個も美味しい順にソートしておく）
交換するのは、現時点で食べようと思っている寿司のうち、同じ種類のものが二つ以上あるものに限る。なぜなら、今確保している寿司よりも、残りのN-K個の寿司の方が美味しさが小さいため、純粋な一種類・一個の寿司のトレードで満足度を向上させられない（種類ボーナスは増えないし、美味しさが減るだけ）からである。
これを、現状2個以上残っている寿司の美味しさをheapqで持っておき、新たな寿司のネタと交換することで、美味しさを増やせるかどうかを見るだけ。種類が多くなればなるほど満足度が増える訳ではないことに注意。
閉路検出。BFSするだけだけどもっとマシなコード（実装法）が知りたい。
n,m = map(int,input().split()) graph = [[] for i in range(n)] for i in range(m): u,v = map(int,input().split()) graph[u-1].append(v-1) graph[v-1].append(u-1) visited = [0]*n ans = 0 start = 0 while sum(visited) != n: while visited[start] == 1: start += 1 stack = [start] flag = True while len(stack) != 0: t = stack.pop() if visited[t] == 0: visited[t] = 1 for j in range(len(graph[t])): if visited[graph[t][j]] == 0: if graph[t][j] not in stack: stack.append(graph[t][j]) else: flag = False if flag: ans += 1 print(ans)
完全グラフから、nがoddなら[1,n-1]...を、nがevenなら[1,n],[2,n-1]...を除けばいい
は？？？？？
縦方向と横方向を一緒くたに考えようとすると混乱するので分解する。
とにかく「ゲーム終了時に盤面上に残っているには、最初にどこに駒があればいいのか？」を考えるため、操作を逆順に遡っていく。
先攻は「範囲を狭めようとする」動きをするのであんまり考えなくていいが、後手が結構ややこしい。
例えば、縦方向に見ていて先手を見終わって範囲が[2,3]だった時に（範囲は1~hとする）、後手が"D"を持ってきたら、後手がDを出して[2,3]の範囲に居られるようにするためには、後手の行動前に駒が[1,2,3]のどこかにいなくちゃいけないな〜みたいに、「後手が行動する前に駒はどこにあるべきか？」を考える。
