結果

問題 No.1553 Lovely City
ユーザー shotoyoo
提出日時 2021-06-18 23:30:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,194 ms / 2,000 ms
コード長 2,816 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 82,140 KB
実行使用メモリ 178,284 KB
最終ジャッジ日時 2024-06-22 21:32:32
合計ジャッジ時間 24,705 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))
class UF:
# unionfind
def __init__(self, n):
self.n = n
self.parent = list(range(n))
self.size = [1] * n
def check(self):
return [self.root(i) for i in range(self.n)]
def root(self, i):
inter = set()
while self.parent[i]!=i:
inter.add(i)
i = self.parent[i]
r = i
for i in inter:
self.parent[i] = r
return r
def connect(self, i, j):
#
ri = self.root(i)
rj = self.root(j)
if ri==rj:
return False
if self.size[ri]<self.size[rj]:
self.parent[ri] = rj
self.size[rj] += self.size[ri]
else:
self.parent[rj] = ri
self.size[ri] += self.size[rj]
return True
#
n,m = map(int, input().split())
ns = [[] for _ in range(n)]
rns = [[] for _ in range(n)]
ds = [0]*n
uf = UF(n)
for _ in range(m):
u,v = map(int, input().split())
u -= 1
v -= 1
ns[u].append(v)
rns[v].append(u)
ds[u] += 1
uf.connect(u,v)
def cycle(rns, ds):
"""0
DAGTPS
rns:
ds:
vs:
done:
"""
n = len(rns)
ans = []
done = [False] * n
from collections import deque
q = deque()
for u in range(n):
if ds[u]==0:
q.append(u)
done[u] = True
vs = []
while q:
u = q.popleft()
vs.append(u)
for v in rns[u]:
if done[v]:
continue
ds[v] -= 1
if ds[v]==0:
done[v] = True
q.append(v)
return vs,done
d = {}
for u in range(n):
r = uf.root(u)
d.setdefault(r, [])
d[r].append(u)
ans = []
for r,l in d.items():
u2v = {}
nns = [[] for _ in range(len(l))]
dds = [0]*len(l)
for i,u in enumerate(l):
u2v[u] = i
dds[i] = ds[u]
for u in l:
i = u2v[u]
nns[i] = [u2v[rns[u][j]] for j in range(len(rns[u]))]
vs, done = cycle(nns, dds)
# print(vs, done)
if all(done):
ll = []
for i in range(len(vs)-1)[::-1]:
ll.append((l[vs[i+1]]+1, l[vs[i]]+1))
ans.extend(ll)
else:
ll = [(l[i]+1, l[(i+1)%len(l)]+1) for i in range(len(l))]
ans.extend(ll)
print(len(ans))
write("\n".join([" ".join(map(str, item)) for item in ans]))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0