Submission #7335008
Source Code Expand
#C問題
#UnionFind(normal)
class UnionFind():
# 作りたい要素数nで初期化
# 使用するインスタンス変数の初期化
def __init__(self, n):
self.n = n
# root[x]<0ならそのノードが根かつその値が木の要素数
# rootノードでその木の要素数を記録する
self.root = [-1]*(n+1)
# 木をくっつける時にアンバランスにならないように調整する
self.rnk = [0]*(n+1)
# ノードxのrootノードを見つける
def Find_Root(self, x):
if(self.root[x] < 0):
return x
else:
# ここで代入しておくことで、後の繰り返しを避ける
self.root[x] = self.Find_Root(self.root[x])
return self.root[x]
# 木の併合、入力は併合したい各ノード
def Unite(self, x, y):
# 入力ノードのrootノードを見つける
x = self.Find_Root(x)
y = self.Find_Root(y)
# すでに同じ木に属していた場合
if(x == y):
return
# 違う木に属していた場合rnkを見てくっつける方を決める
elif(self.rnk[x] > self.rnk[y]):
self.root[x] += self.root[y]
self.root[y] = x
else:
self.root[y] += self.root[x]
self.root[x] = y
# rnkが同じ(深さに差がない場合)は1増やす
if(self.rnk[x] == self.rnk[y]):
self.rnk[y] += 1
# xとyが同じグループに属するか判断
def isSameGroup(self, x, y):
return self.Find_Root(x) == self.Find_Root(y)
# ノードxが属する木のサイズを返す
def Count(self, x):
return -self.root[self.Find_Root(x)]
"""
実装例
ABC126E 1or2
#E問題
#UnionFind(normal)
UFコードは省略
if __name__ == "__main__":
N,M = map(int,input().split())
uf = UnionFind(N+1)
for i in range(M):
X,Y,Z = map(int,input().split())
if not uf.isSameGroup(X,Y):
uf.Unite(X,Y)
ans=0
for j in uf.root[1:N+1]:
if j < 0:
ans+=1
print(ans)
"""
N,M = map(int,input().split())
edges = []
for i in range(N):
Linput = list(map(int,input().split()))
k = Linput[0]
for j in range(k):
L = Linput[j+1]+N-1
edges.append([i,L])
uf = UnionFind(N+M)
for edge in edges:
x,y = edge[0],edge[1]
if not uf.isSameGroup(x,y):
uf.Unite(x,y)
flag = 0
for i in range(N-1):
I = i+1
if not uf.isSameGroup(0,I):
flag = 1
break
print("YES" if flag == 0 else "NO")
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
OribeYasuna |
Language |
Python (3.4.3) |
Score |
400 |
Code Size |
2775 Byte |
Status |
AC |
Exec Time |
785 ms |
Memory |
23216 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
200 / 200 |
200 / 200 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
dataset1 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt |
dataset2 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
17 ms |
3188 KB |
01-02.txt |
AC |
20 ms |
3188 KB |
01-03.txt |
AC |
23 ms |
3188 KB |
01-04.txt |
AC |
25 ms |
3188 KB |
01-05.txt |
AC |
23 ms |
3188 KB |
01-06.txt |
AC |
23 ms |
3188 KB |
01-07.txt |
AC |
23 ms |
3188 KB |
01-08.txt |
AC |
23 ms |
3188 KB |
01-09.txt |
AC |
23 ms |
3188 KB |
01-10.txt |
AC |
24 ms |
3188 KB |
02-01.txt |
AC |
339 ms |
18416 KB |
02-02.txt |
AC |
671 ms |
21564 KB |
02-03.txt |
AC |
354 ms |
17780 KB |
02-04.txt |
AC |
653 ms |
21032 KB |
02-05.txt |
AC |
728 ms |
20900 KB |
02-06.txt |
AC |
580 ms |
20912 KB |
02-07.txt |
AC |
785 ms |
21432 KB |
02-08.txt |
AC |
631 ms |
21748 KB |
02-09.txt |
AC |
770 ms |
23216 KB |
02-10.txt |
AC |
548 ms |
19920 KB |
02-11.txt |
AC |
496 ms |
19944 KB |
02-12.txt |
AC |
557 ms |
19260 KB |
02-13.txt |
AC |
491 ms |
19284 KB |
sample-01.txt |
AC |
17 ms |
3064 KB |
sample-02.txt |
AC |
17 ms |
3064 KB |