結果

問題 No.2286 Join Hands
ユーザー 👑 rin204
提出日時 2024-04-29 22:08:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 265 ms / 2,000 ms
コード長 5,023 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 97,260 KB
最終ジャッジ日時 2024-11-19 06:36:00
合計ジャッジ時間 11,915 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class UnionFind:
def __init__(self, n):
self.n = n
self.par = [-1] * n
self.group_ = n
def find(self, x):
if self.par[x] < 0:
return x
lst = []
while self.par[x] >= 0:
lst.append(x)
x = self.par[x]
for y in lst:
self.par[y] = x
return x
def unite(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return False
if self.par[x] > self.par[y]:
x, y = y, x
self.par[x] += self.par[y]
self.par[y] = x
self.group_ -= 1
return True
def size(self, x):
return -self.par[self.find(x)]
def same(self, x, y):
return self.find(x) == self.find(y)
@property
def group(self):
return self.group_
from collections import deque
import sys
from dataclasses import dataclass
sys.setrecursionlimit(10**7)
class mf_graph:
@dataclass
class edge:
from_: int
to: int
cap: int
flow: int
# def __init__(self, from_, to, cap, flow):
# self.from_ = from_
# self.to = to
# self.cap = cap
# self.flow = flow
@dataclass
class _edge:
to: int
rev: int
cap: int
# def __init__(self, to, rev, cap):
# self.to = to
# self.rev = rev
# self.cap = cap
def __init__(self, n):
self.n = n
self.G = [[] for _ in range(n)]
self.pos = []
def add_edge(self, from_, to, cap):
m = len(self.pos)
self.pos.append((from_, len(self.G[from_])))
from_id = len(self.G[from_])
to_id = len(self.G[to])
if from_ == to:
to_id += 1
self.G[from_].append(mf_graph._edge(to, to_id, cap))
self.G[to].append(mf_graph._edge(from_, from_id, 0))
return m
def get_edge(self, i):
_e = self.G[self.pos[i][0]][self.pos[i][1]]
_re = self.G[_e.to][_e.rev]
return mf_graph.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)
def edges(self):
m = len(self.pos)
result = []
for i in range(m):
result.append(self.get_edge(i))
return result
def change_edge(self, i, new_cap, new_flow):
_e = self.G[self.pos[i][0]][self.pos[i][1]]
self.G[_e.to][_e.rev].cap = new_flow
self.G[self.pos[i][0]][self.pos[i][1]].cap = new_cap - new_flow
def flow(self, s, t, flow_limit=1 << 60):
level = []
iter = []
que = deque()
def bfs():
nonlocal level
level = [-1] * self.n
level[s] = 0
que.clear()
que.append(s)
while que:
v = que.popleft()
for e in self.G[v]:
if e.cap == 0 or level[e.to] >= 0:
continue
level[e.to] = level[v] + 1
if e.to == t:
return
que.append(e.to)
def dfs(v, up):
if v == s:
return up
nonlocal level, iter
res = 0
level_v = level[v]
while iter[v] < len(self.G[v]):
i = iter[v]
iter[v] += 1
e = self.G[v][i]
if level_v <= level[e.to] or self.G[e.to][e.rev].cap == 0:
continue
d = dfs(e.to, min(up - res, self.G[e.to][e.rev].cap))
if d <= 0:
continue
self.G[v][i].cap += d
self.G[e.to][e.rev].cap -= d
res += d
if res == up:
return res
level[v] = self.n
return res
flow = 0
while flow < flow_limit:
bfs()
if level[t] == -1:
break
iter = [0] * self.n
f = dfs(t, flow_limit - flow)
if f == 0:
break
flow += f
return flow
def min_cut(self, s):
visited = [False] * self.n
que = deque()
que.append(s)
while que:
p = que.popleft()
visited[p] = True
for e in self.G[p]:
if e.cap and not visited[e.to]:
visited[e.to] = True
que.append(e.to)
return visited
n, m = map(int, input().split())
G = mf_graph(2 * n + 2)
s = 2 * n
t = s + 1
for i in range(n):
G.add_edge(s, i, 1)
G.add_edge(n + i, t, 1)
E = []
for i in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
E.append((u, v))
G.add_edge(u, n + v, 1)
G.add_edge(v, n + u, 1)
res = G.flow(s, t)
if res == n - 1:
UF = UnionFind(n)
for u, v in E:
UF.unite(u, v)
if any(UF.size(i) == 1 for i in range(n)):
res = n - 2
ans = res - (n - res)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0