AtCoder Beginner Contest 241（Sponsored by Panasonic）D,G問題メモ

from collections import deque
from itertools import accumulate
from typing import List, Tuple


class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """

    def __init__(self, n: int):
        self.n = n
        self.edges: List[List[int]] = []  # [from, to, capacity]
        self.links: List[List[int]] = [[] for _ in range(n)]
        # if exists an edge (u -> v) with capacity...
        #   links[u] = [ i, j, ...]
        #         ,------'
        #   edges[i] = [u, v, capacity]
        # Reverse edge is i^1

    def add_link(self, from_: int, to: int, capacity: int) -> None:
        li = len(self.edges)
        self.links[from_].append(li)
        self.links[to].append(li + 1)
        self.edges.append([from_, to, capacity])
        self.edges.append([to, from_, 0])

    def reset_link(self):
        """ 一回流したフローを初期化する """
        edges = self.edges
        for li in range(0, len(edges), 2):
            edges[li][2] += edges[li ^ 1][2]
            edges[li ^ 1][2] = 0

    def change_link(self, from_: int, to: int, new_capacity: int):
        """ リンクコストを変更する。流す前またはリセット後に呼ぶこと """
        for li in self.links[from_]:
            if li & 1 == 1:
                continue
            if self.edges[li][1] == to:
                self.edges[li][2] = new_capacity
                break
        else:
            assert RuntimeWarning(f'No edge {from_} -> {to}')

    def bfs(self, s: int) -> List[int]:
        links = self.links
        edges = self.edges
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for li in links[v]:
                _, to, cap = edges[li]
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth

    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        edges = self.edges
        stack = [s]

        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                li = links[v][i]
                _, to, cap = edges[li]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0

        f = 1 << 60
        used_links = []
        for v in stack[:-1]:
            li = links[v][progress[v]]
            _, to, cap = edges[li]
            f = min(f, cap)
            used_links.append(li)

        for li in used_links:
            edges[li][2] -= f
            edges[li ^ 1][2] += f

        return f

    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow

    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        links = self.links
        edges = self.edges
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for li in links[v]:
                _, u, cap = edges[li]
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        cut_edges = []
        for u, v, cap in edges[::2]:
            if reachable[u] == 1 and reachable[v] == 0:
                cut_edges.append((u, v))
        return cut_edges


n, m = map(int, input().split())
win_count = [0] * n
rem_match = [set(range(n)) - {i} for i in range(n)]
for _ in range(m):
    w, l = map(int, input().split())
    w -= 1
    l -= 1
    win_count[w] += 1
    rem_match[w].remove(l)
    rem_match[l].remove(w)

all_rem_match = []
idx_rem_match = {}

for i in range(n):
    for j in rem_match[i]:
        if i < j:
            k = len(all_rem_match)
            all_rem_match.append((i, j))
            idx_rem_match[i, j] = idx_rem_match[j, i] = k

arm = len(all_rem_match)  # remaining match count

mf = Dinic(n + arm + 2)
s = n + arm
t = s + 1

for i in range(n):
    mf.add_link(s, i, 0)

for k, (i, j) in enumerate(all_rem_match):
    mf.add_link(i, k + n, 1)
    mf.add_link(j, k + n, 1)
    mf.add_link(k + n, t, 1)

fwd_max = [0]
fwd_max.extend(accumulate(win_count, func=max))
bwd_max = [0]
bwd_max.extend(accumulate(reversed(win_count), func=max))
bwd_max.reverse()

ans = []
for i in range(n):
    rem = rem_match[i]
    max_win = win_count[i] + len(rem)
    if max_win <= max(fwd_max[i], bwd_max[i + 1]):
        continue
    for j in range(n):
        if i == j:
            mf.change_link(s, j, 0)
        else:
            mf.change_link(s, j, max_win - 1 - win_count[j])
    for j in rem:
        k = idx_rem_match[i, j]
        mf.change_link(j, k + n, 0)

    if mf.max_flow(s, t) >= arm - len(rem):
        ans.append(i + 1)

    mf.reset_link()
    for j in rem:
        k = idx_rem_match[i, j]
        mf.change_link(j, k + n, 1)

print(*ans)