結果
問題 |
No.1605 Matrix Shape
|
ユーザー |
![]() |
提出日時 | 2025-03-20 21:11:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 987 ms / 2,000 ms |
コード長 | 2,070 bytes |
コンパイル時間 | 410 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 177,924 KB |
最終ジャッジ日時 | 2025-03-20 21:12:21 |
合計ジャッジ時間 | 13,131 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sys from sys import stdin from collections import defaultdict sys.setrecursionlimit(1 << 25) class UnionFind: def __init__(self): self.parent = dict() self.rank = dict() def find(self, x): if x not in self.parent: self.parent[x] = x self.rank[x] = 1 if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root == y_root: return if self.rank[x_root] < self.rank[y_root]: self.parent[x_root] = y_root else: self.parent[y_root] = x_root if self.rank[x_root] == self.rank[y_root]: self.rank[x_root] +=1 def main(): n = int(stdin.readline()) uf = UnionFind() nodes = set() out_degree = defaultdict(int) in_degree = defaultdict(int) for _ in range(n): h, w = map(int, stdin.readline().split()) nodes.add(h) nodes.add(w) out_degree[h] +=1 in_degree[w] +=1 uf.union(h, w) # Check connected node_list = list(nodes) if not node_list: print(0) return root = uf.find(node_list[0]) for node in node_list[1:]: if uf.find(node) != root: print(0) return # Check Euler conditions count_start = 0 count_end = 0 valid = True for node in nodes: delta = out_degree[node] - in_degree[node] if delta == 1: count_start +=1 elif delta == -1: count_end +=1 elif delta != 0: valid = False if not valid or count_start >1 or count_end >1: print(0) return if count_start == 0 and count_end ==0: # Eulerian circuit, number of nodes is the answer print(len(nodes)) elif count_start ==1 and count_end ==1: print(1) else: print(0) if __name__ == "__main__": main()