結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
class UnionFind():def __init__(self, n):self.n = nself.PA = [-1] * ndef root(self, a):L = []while self.PA[a] >= 0:L.append(a)a = self.PA[a]for l in L:self.PA[l] = areturn adef 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] = raelse:self.PA[rb] += self.PA[ra]self.PA[ra] = rbdef 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 = 0GG = []I = [-1] * self.nfor i in range(self.n):if G[i]:GG.append(G[i])I[i] = cntcnt += 1return GG, Idef 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 -> 2ct = 0for i0 in range(n):if done[i0]: continueQ = [~i0, i0]while Q:i = Q.pop()if i < 0:if done[~i] == 2: continuedone[~i] = 2T.append(~i)ct += 1continueif i >= 0:if done[i]: continuedone[i] = 1for j in E[i]:if done[j]: continueQ.append(~j)Q.append(j)done = [0] * nSCC = []### ID が必要なときI = [0] * n###for i0 in T[::-1]:if done[i0]: continueL = []Q = [~i0, i0]while Q:i = Q.pop()if i < 0:if done[~i] == 2: continuedone[~i] = 2L.append(~i)###I[~i] = len(SCC)###continueif i >= 0:if done[i]: continuedone[i] = 1for j in iE[i]:if done[j]: continueQ.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, iEimport sysinput = 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))