AtCoder Regular Contest 097

Submission #3971350

Source codeソースコード

N,M = map(int,input().split())
p = [int(i) for i in input().split()]
xy = []

for _ in range(M):
    xy.append(list(map(int,input().split())))

par = [0 for _ in range(N+1)]
rank = [0 for _ in range(N+1)]

def init(n):
    for i in range(n):
        par[i] = i
        rank[i] = 0
def find(x):
    if par[x] ==x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x,y):
    x = find(x)
    y = find(y)
    if x==y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def same(x,y):
    return True if find(x) == find(y) else False

init(N+1)
for x,y in xy:
    unite(x,y)
count = 0
for i in p:
    if same(i,p[i-1]):
        count += 1
print(count)

Submission

Task問題 D - Equals
User nameユーザ名 sgtukk0128
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 400
Source lengthソースコード長 822 Byte
File nameファイル名
Exec time実行時間 653 ms
Memory usageメモリ使用量 36092 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt,0_003.txt
All 400 / 400 0_000.txt,0_001.txt,0_002.txt,0_003.txt,1_004.txt,1_005.txt,1_006.txt,1_007.txt,1_008.txt,1_009.txt,1_010.txt,1_011.txt,1_012.txt,1_013.txt,1_014.txt,1_015.txt,1_016.txt,1_017.txt,1_018.txt,1_019.txt,1_020.txt,1_021.txt,1_022.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt AC 18 ms 3064 KB
0_001.txt AC 18 ms 3064 KB
0_002.txt AC 18 ms 3064 KB
0_003.txt AC 21 ms 3064 KB
1_004.txt AC 425 ms 23716 KB
1_005.txt AC 544 ms 36012 KB
1_006.txt AC 653 ms 36092 KB
1_007.txt AC 18 ms 3064 KB
1_008.txt AC 18 ms 3064 KB
1_009.txt AC 18 ms 3064 KB
1_010.txt AC 18 ms 3064 KB
1_011.txt AC 18 ms 3064 KB
1_012.txt AC 19 ms 3064 KB
1_013.txt AC 22 ms 3188 KB
1_014.txt AC 39 ms 3828 KB
1_015.txt AC 19 ms 3064 KB
1_016.txt AC 19 ms 3064 KB
1_017.txt AC 23 ms 3316 KB
1_018.txt AC 390 ms 23732 KB
1_019.txt AC 117 ms 13812 KB
1_020.txt AC 116 ms 13812 KB
1_021.txt AC 119 ms 13812 KB
1_022.txt AC 614 ms 36016 KB