結果
問題 | No.1813 Magical Stones |
ユーザー |
![]() |
提出日時 | 2021-09-19 13:02:22 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,537 ms / 2,000 ms |
コード長 | 1,906 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 59,136 KB |
最終ジャッジ日時 | 2024-07-16 06:55:31 |
合計ジャッジ時間 | 26,433 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
class SCC: 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(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 """ Main Code """ n,m = map(int,input().split()) scc = SCC(n) for _ in range(m): a,b = map(int,input().split()) scc.add_edge(a-1,b-1) scc.build() DAG,_ = scc.construct() t = len(DAG) if(t <= 1): print(0) exit(0) source = [True]*t sink = [True]*t for i in range(t): for j in DAG[i]: sink[i] = source[j] = False source_cnt = sum(i for i in source) sink_cnt = sum(i for i in sink) ans = max(source_cnt,sink_cnt) print(ans)