結果

問題 No.1553 Lovely City
ユーザー Kiri8128Kiri8128
提出日時 2021-06-18 22:49:06
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,057 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 206,216 KB
最終ジャッジ日時 2024-06-22 21:09:21
合計ジャッジ時間 19,312 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 4 RE * 22
権限があれば一括ダウンロードができます

ソースコード

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

class UnionFind():
def __init__(self, n):
self.n = n
self.PA = [-1] * n
def root(self, a):
L = []
while self.PA[a] >= 0:
L.append(a)
a = self.PA[a]
for l in L:
self.PA[l] = a
return a
def unite(self, a, b):
ra, rb = self.root(a), self.root(b)
if ra != rb:
if self.PA[rb] >= self.PA[ra]:
self.PA[ra] += self.PA[rb]
self.PA[rb] = ra
else:
self.PA[rb] += self.PA[ra]
self.PA[ra] = rb
def size(self, a):
return -self.PA[self.root(a)]
def groups(self):
G = [[] for _ in range(self.n)]
for i in range(self.n):
G[self.root(i)].append(i)
return [g for g in G if g]
def groups_index(self):
G = [[] for _ in range(self.n)]
for i in range(self.n):
G[self.root(i)].append(i)
cnt = 0
GG = []
I = [-1] * self.n
for i in range(self.n):
if G[i]:
GG.append(G[i])
I[i] = cnt
cnt += 1
return GG, I
def group_size(self):
G = [[] for _ in range(self.n)]
for i in range(self.n):
G[self.root(i)].append(i)
return [len(g) for g in G if g]
def scc(E):
n = len(E)
iE = [[] for _ in range(n)]
for i, e in enumerate(E):
for v in e:
iE[v].append(i)
T = []
done = [0] * n # 0 -> 1 -> 2
ct = 0
for i0 in range(n):
if done[i0]: continue
Q = [~i0, i0]
while Q:
i = Q.pop()
if i < 0:
if done[~i] == 2: continue
done[~i] = 2
T.append(~i)
ct += 1
continue
if i >= 0:
if done[i]: continue
done[i] = 1
for j in E[i]:
if done[j]: continue
Q.append(~j)
Q.append(j)
done = [0] * n
SCC = []
### ID
I = [0] * n
###
for i0 in T[::-1]:
if done[i0]: continue
L = []
Q = [~i0, i0]
while Q:
i = Q.pop()
if i < 0:
if done[~i] == 2: continue
done[~i] = 2
L.append(~i)
###
I[~i] = len(SCC)
###
continue
if i >= 0:
if done[i]: continue
done[i] = 1
for j in iE[i]:
if done[j]: continue
Q.append(~j)
Q.append(j)
SCC.append(L)
return SCC, I
### ↓ Edge return
nE = [set() for _ in range(len(SCC))]
iE = [set() for _ in range(len(SCC))]
for i, e in enumerate(E):
for j in e:
if I[i] == I[j]: continue
# print("i, j, I[i], I[j] =", i, j, I[i], I[j])
nE[I[i]].add(I[j])
iE[I[j]].add(I[i])
nE = [list(e) for e in nE]
iE = [list(e) for e in iE]
return SCC, I, nE, iE
import sys
input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
X = []
for _ in range(M):
a, b = map(int, input().split())
X.append((a-1, b-1))
uf = UnionFind(N)
for a, b in X:
uf.unite(a, b)
# G = uf.groups()
# print(G)
GG, I = uf.groups_index()
K = len(GG)
D = [{v: f for f, v in enumerate(GG[i])} for i in range(K)]
XX = [[] for _ in range(K)]
for a, b in X:
g = I[uf.root(a)]
XX[g].append((D[g][a], D[g][b]))
ANS = []
for i in range(K):
gg = GG[i]
si = len(gg)
E = [[] for _ in range(si)]
for a, b in XX[i]:
E[a].append(b)
SCC, II = scc(E)
if len(SCC) < si:
for j in range(si):
ANS.append((gg[j-1], gg[j]))
else:
for j in range(si - 1):
ANS.append(str(gg[SCC[j][0]] + 1) + " " + str(gg[SCC[j+1][0]] + 1))
print(len(ANS))
print("\n".join(ANS))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0