結果
問題 |
No.1605 Matrix Shape
|
ユーザー |
![]() |
提出日時 | 2021-07-17 00:33:10 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 562 ms / 2,000 ms |
コード長 | 2,108 bytes |
コンパイル時間 | 246 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 33,384 KB |
最終ジャッジ日時 | 2024-07-06 12:05:48 |
合計ジャッジ時間 | 11,193 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sys sys.setrecursionlimit(200005) int1 = lambda x: int(x)-1 p2D = lambda x: print(*x, sep="\n") def II(): return int(sys.stdin.readline()) def LI(): return list(map(int, sys.stdin.readline().split())) def LI1(): return list(map(int1, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def LLI1(rows_number): return [LI1() for _ in range(rows_number)] def SI(): return sys.stdin.readline().rstrip() # dij = [(0, 1), (-1, 0), (0, -1), (1, 0)] dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)] inf = 10**16 md = 998244353 # md = 10**9+7 class UnionFind: def __init__(self, n): self.state = [-1]*n self.size_table = [1]*n # cntはグループ数 self.cnt = n def root(self, u): stack = [] while self.state[u] >= 0: stack.append(u) u = self.state[u] for v in stack: self.state[v] = u return u def merge(self, u, v): u = self.root(u) v = self.root(v) if u == v: return du = -self.state[u] dv = -self.state[v] if du < dv: u, v = v, u if du == dv: self.state[u] -= 1 self.state[v] = u self.cnt -= 1 self.size_table[u] += self.size_table[v] return # グループの要素数 def size(self, u): return self.size_table[self.root(u)] mx=200005 # mx = 20 n = II() uf = UnionFind(mx) deg = [0]*mx st = set() u = -1 for i in range(n): h, w = LI() deg[h] -= 1 deg[w] += 1 uf.merge(h, w) st.add(h) st.add(w) u = h def findsg(): if uf.size(u) != len(st): return -2, -2 s = g = -1 for v in range(mx): if abs(deg[v]) > 1: return -2, -2 if deg[v] == 1: if s == -1: s = v else: return -2, -2 if deg[v] == -1: if g == -1: g = v else: return -2, -2 return s, g s, g = findsg() if s == -2: print(0) elif s == -1: print(len(st)) else: print(1)