#651470 (PyPy3) No.1605 Matrix Shape

• 問題: No.1605 Matrix Shape
• ユーザー: 👑 SPD_9X2
• 提出日時: 2021-04-25 21:26:27
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 354 ms / 2,000 ms
• コード長: 2,150 bytes
• コンパイル時間: 147 ms
• コンパイル使用メモリ: 82,236 KB
• 実行使用メモリ: 101,840 KB
• 最終ジャッジ日時: 2024-07-06 07:50:28
• 合計ジャッジ時間: 8,340 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 34

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
"""
想定解 ver_1.0
H*W を H-W の辺とするグラフで考える
連結でない場合、答えは0
そうでない場合、入次数と出次数を考える
入次 - 出次数 を考える
+1 , -1　が1つずつあり、他全部 0の場合、答えは 1
全部 0 の時、答えは 数字の種類数
そうでなければ 0
"""
import sys
from sys import stdin
def uf_find(n,p):
    ufl = []
    while p[n] != n:
        ufl.append(n)
        n = p[n]
    for i in ufl:
        p[i] = n
    return n
def uf_union(a,b,p,rank):
    ap = uf_find(a,p)
    bp = uf_find(b,p)
    if ap == bp:
        return False
    else:
        if rank[ap] > rank[bp]:
            p[bp] = ap
        elif rank[ap] < rank[bp]:
            p[ap] = bp
        else:
            p[bp] = ap
            rank[ap] += 1
        return True
N = int(stdin.readline())
assert 2 <= N <= 2*(10**5)
in_num = {}   #相対入次数
merge_num = 0 #ufでマージした回数
p = [i for i in range(200001)]
rank = [0] * (200001)
for i in range(N):
    H,W = map(int,stdin.readline().split())
    assert 1 <= H <= 2*(10**5)
    assert 1 <= W <= 2*(10**5)
    if H not in in_num:
        in_num[H] = 0
    if W not in in_num:
        in_num[W] = 0
    #相対入次数を変更
    in_num[H] -= 1
    in_num[W] += 1
    #union-findでマージ
    if uf_union(H,W,p,rank):
        merge_num += 1
num_0 = 0 #0の数
num_1 = 0 #1の数
num_minus_1 = 0 #-1の数
num_other = 0   #他の数字の数
for i in in_num:
    if in_num[i] == 0:
        num_0 += 1
    elif in_num[i] == 1:
        num_1 += 1
    elif in_num[i] == -1:
        num_minus_1 += 1
    else:
        num_other += 1
#ここから答えの判定
#連結でない場合は、0
if merge_num != len(in_num)-1:
    print (0)
    sys.exit()
#0,-1,1以外があったら0
if num_other > 0: 
    print (0)
    sys.exit()
#-1,1が1個づつあったら 1
if num_1 == 1 and num_minus_1 == 1:
    print (1)
    sys.exit()
#全て0なら、登場した数字全て
if num_1 == 0 and num_1 == 0 and num_minus_1 == 0:
    print (num_0)
    sys.exit()
#そうでないなら、0
print (0)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX