結果
問題 | No.1553 Lovely City |
ユーザー | neterukun |
提出日時 | 2021-06-18 21:49:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,718 ms / 2,000 ms |
コード長 | 3,551 bytes |
コンパイル時間 | 446 ms |
コンパイル使用メモリ | 86,776 KB |
実行使用メモリ | 245,276 KB |
最終ジャッジ日時 | 2023-09-04 22:47:08 |
合計ジャッジ時間 | 35,589 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
71,280 KB |
testcase_01 | AC | 75 ms
71,460 KB |
testcase_02 | AC | 484 ms
163,992 KB |
testcase_03 | AC | 86 ms
71,188 KB |
testcase_04 | AC | 85 ms
71,452 KB |
testcase_05 | AC | 98 ms
76,324 KB |
testcase_06 | AC | 100 ms
76,196 KB |
testcase_07 | AC | 90 ms
75,348 KB |
testcase_08 | AC | 1,151 ms
168,468 KB |
testcase_09 | AC | 1,237 ms
172,264 KB |
testcase_10 | AC | 1,336 ms
200,824 KB |
testcase_11 | AC | 1,098 ms
167,548 KB |
testcase_12 | AC | 1,339 ms
211,916 KB |
testcase_13 | AC | 1,087 ms
153,804 KB |
testcase_14 | AC | 1,186 ms
173,164 KB |
testcase_15 | AC | 1,163 ms
175,236 KB |
testcase_16 | AC | 1,288 ms
182,748 KB |
testcase_17 | AC | 1,093 ms
174,556 KB |
testcase_18 | AC | 1,616 ms
227,624 KB |
testcase_19 | AC | 1,686 ms
237,808 KB |
testcase_20 | AC | 1,718 ms
245,032 KB |
testcase_21 | AC | 1,633 ms
236,152 KB |
testcase_22 | AC | 1,643 ms
242,760 KB |
testcase_23 | AC | 1,653 ms
243,672 KB |
testcase_24 | AC | 1,711 ms
244,528 KB |
testcase_25 | AC | 1,652 ms
245,276 KB |
testcase_26 | AC | 1,606 ms
235,916 KB |
testcase_27 | AC | 1,625 ms
225,500 KB |
ソースコード
class UnionFind: def __init__(self, n): self.parent = [-1] * n self.n = n self.cnt = n def root(self, x): if self.parent[x] < 0: return x else: self.parent[x] = self.root(self.parent[x]) return self.parent[x] def merge(self, x, y): x = self.root(x) y = self.root(y) if x == y: return False if self.parent[x] > self.parent[y]: x, y = y, x self.parent[x] += self.parent[y] self.parent[y] = x self.cnt -= 1 return True def same(self, x, y): return self.root(x) == self.root(y) def size(self, x): return -self.parent[self.root(x)] def count(self): return self.cnt def groups(self): res = [[] for _ in range(self.n)] for i in range(self.n): res[self.root(i)].append(i) return [group for group in res if group] class StronglyConnectedComponents: def __init__(self, n): self.n = n self.graph = [[] for _ in range(n)] self.rev_graph = [[] for _ in range(n)] self.labels = [-1] * n self.lb_cnt = 0 def add_edge(self, v, nxt_v): self.graph[v].append(nxt_v) self.rev_graph[nxt_v].append(v) def build(self): self.post_order = [] self.used = [False] * self.n for v in range(self.n): if not self.used[v]: self._dfs(v) for v in reversed(self.post_order): if self.labels[v] == -1: self._rev_dfs(v) self.lb_cnt += 1 def _dfs(self, v): stack = [v, 0] while stack: v, idx = stack[-2:] if not idx and self.used[v]: stack.pop() stack.pop() else: self.used[v] = True if idx < len(self.graph[v]): stack[-1] += 1 stack.append(self.graph[v][idx]) stack.append(0) else: stack.pop() self.post_order.append(stack.pop()) def _rev_dfs(self, v): stack = [v] self.labels[v] = self.lb_cnt while stack: v = stack.pop() for nxt_v in self.rev_graph[v]: if self.labels[nxt_v] != -1: continue stack.append(nxt_v) self.labels[nxt_v] = self.lb_cnt def construct_dag(self): self.dag = [[] for i in range(self.lb_cnt)] self.groups = [[] for i in range(self.lb_cnt)] for v, lb in enumerate(self.labels): for nxt_v in self.graph[v]: nxt_lb = self.labels[nxt_v] if lb == nxt_lb: continue self.dag[lb].append(nxt_lb) self.groups[lb].append(v) return self.dag, self.groups n, m = map(int, input().split()) edges = [list(map(int, input().split())) for i in range(m)] scc = StronglyConnectedComponents(n) uf = UnionFind(n) for u, v in edges: u -= 1 v -= 1 scc.add_edge(u, v) uf.merge(u, v) scc.build() dag, group = scc.construct_dag() ans = [] for gp in uf.groups(): gp = sorted(gp, key=lambda x: scc.labels[x]) lb = [scc.labels[i] for i in gp] for i in range(len(gp) - 1): ans.append((gp[i], gp[i + 1])) if len(set(lb)) != len(lb): ans.append((gp[-1], gp[0])) print(len(ans)) for u, v in ans: print(u + 1, v + 1)