結果
問題 | No.1813 Magical Stones |
ユーザー |
![]() |
提出日時 | 2024-11-30 21:58:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 493 ms / 2,000 ms |
コード長 | 2,554 bytes |
コンパイル時間 | 568 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 139,792 KB |
最終ジャッジ日時 | 2024-11-30 21:58:58 |
合計ジャッジ時間 | 11,995 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
import sysinput = sys.stdin.readline"""強連結成分分解(SCC)ref : https://manabitimes.jp/math/1250"""class SCC:def __init__(self, n):self.n = nself.route = [[] for _ in [0] * n]self.rev_route = [[] for _ in [0] * n]self.label = [-1] * nself.count = 0def add_edge(self, v_first, v_second):self.route[v_first].append(v_second)self.rev_route[v_second].append(v_first)def _build(self):self.v_list = []self.visited = set([])for v in range(self.n):if(v in self.visited):continueself._dfs(v)for v in reversed(self.v_list):if(self.label[v] != -1):continueself._rev_dfs(v)self.count += 1def _dfs(self, v_start):stack = [v_start, 0]while(stack):v, id = stack[-2:]if(id == 0 and v in self.visited):stack.pop()stack.pop()continueself.visited.add(v)if(id < len(self.route[v])):stack[-1] += 1stack.extend([self.route[v][id], 0])continuestack.pop()self.v_list.append(stack.pop())def _rev_dfs(self, v_start):stack = [v_start]self.label[v_start] = self.countwhile(stack):v_now = stack.pop()for v_next in self.rev_route[v_now]:if(self.label[v_next] != -1):continueself.label[v_next] = self.countstack.append(v_next)def construct(self):self._build()dag = [[] for _ in [0] * self.count]group = [[] for _ in [0] * self.count]for v, lb in enumerate(self.label):for v_next in self.route[v]:lb_next = self.label[v_next]if(lb == lb_next):continuedag[lb].append(lb_next)group[lb].append(v)return dag, group'''Main Code'''n, m = map(int, input().split())edges = [[x - 1 for x in map(int, input().split())] for _ in [0] * m]scc = SCC(n)for x, y in edges:scc.add_edge(x, y)dag, _ = scc.construct()N = len(dag)if(N == 1):exit(print(0))zero_in = [True] * Nzero_out = [True] * Nfor i in range(N):if(dag[i]):zero_out[i] = Falsefor j in dag[i]:zero_in[j] = Falseans = max(sum(zero_in), sum(zero_out))print(ans)