後ろから考える典型について
- 結果がすべて確定した状態から考える
- 同時に、順方向の条件をAとしたとき、その逆の¬Aが後ろから前に進む条件である
例; 後ろから考える典型
問題
解説
- 結果がすべて確定した状態 = すべて崩落した状態を初期値とする
- 後ろから橋を結合していき、橋の数のグループのサイズの累積値が解になる
解答
# unionfind省略
N, M = map(int, input().split())
AB = []
for _ in range(M):
a, b = map(int, input().split())
a -= 1
b -= 1
AB.append((a, b))
uf = UnionFind(n=N)
ans = [0] # すべて崩落するので初期値は0でよい
for a,b in AB[::-1]:
if uf.find(a) == uf.find(b):
tmp = ans[-1]
else:
tmp = ans[-1] + uf.size(a)*uf.size(b)
ans.append(tmp)
uf.union(a,b)
ans.pop()
max_ = N*(N-1)//2
print(*[max_ -x for x in ans[::-1]], sep="\n")
例; 逆の条件を作るのが難しい例
問題
解説
- ボールA,Bが少なくとも一方が白 かつ ボールiを黒くする -> ボールA = i or B = i or A,Bどちらかが白
- 公式
解答
import collections
N = int(input())
G = [[] for _ in range(N+1)]
que = collections.deque([])
vis = set()
for i in range(1, N+1):
a, b = map(int,input().split())
G[a].append(i)
G[b].append(i)
if a == i or b == i:
vis.add(i)
que.append(i)
trc = []
while que:
pos = que.pop()
trc.append(pos)
for i in G[pos]:
if i in vis:
continue
vis.add(i)
que.append(i)
trc = trc[::-1]
if len(trc) != N:
print(-1)
else:
print(*trc, sep="\n")