結果
問題 | No.1553 Lovely City |
ユーザー |
|
提出日時 | 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 |
ソースコード
import sysinput = 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:# unionfinddef __init__(self, n):self.n = nself.parent = list(range(n))self.size = [1] * ndef 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 = ifor i in inter:self.parent[i] = rreturn rdef connect(self, i, j):# 繋いだかどうかを返すri = self.root(i)rj = self.root(j)if ri==rj:return Falseif self.size[ri]<self.size[rj]:self.parent[ri] = rjself.size[rj] += self.size[ri]else:self.parent[rj] = riself.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]*nuf = UF(n)for _ in range(m):u,v = map(int, input().split())u -= 1v -= 1ns[u].append(v)rns[v].append(u)ds[u] += 1uf.connect(u,v)def cycle(rns, ds):"""出次数0の頂点を削除しつづけるDAGならTPS順序も求まるrns: 逆辺の隣接リストds: もとのグラフにおける出次数返り値vs: 除かれた頂点done: 除いたフラグ"""n = len(rns)ans = []done = [False] * nfrom collections import dequeq = deque()for u in range(n):if ds[u]==0:q.append(u)done[u] = Truevs = []while q:u = q.popleft()vs.append(u)for v in rns[u]:if done[v]:continueds[v] -= 1if ds[v]==0:done[v] = Trueq.append(v)return vs,doned = {}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] = idds[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]))