Problem p03354 (python)

Fixed submission:

class UnionFind():
    def __init__(self, n):
        self.par = []
        for i in range(n+1):
            self.par.append(i)

    def find(self, x):
        if(self.par[x] == x):
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same(self,x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y) :
            return
        self.par[x] = y




n, m = map(int, input().split())
p = list(map(int, input().split()))

uf = UnionFind(n);

for _ in range(m):
    x, y = map(int, input().split())
    uf.union(x, y)


count = 0
for index in range(n):
    start = index + 1
    to = p[index]
    if uf.same(start, to):
        count += 1
print(count)

Buggy submission (verdict: Runtime Error):

from collections import defaultdict

from copy import deepcopy


n, m = map(int, input().split())
p = list(map(int, input().split()))


def dp(start, to, used):
    cused = deepcopy(used)
    if start == to:
        return True
    if start in x_y:
        is_ok = False
        for next_start in x_y[start]:
            if not next_start in used:
                #remove used
                used.append(next_start)
                if dp(next_start, to, cused):
                    return True
        return is_ok

    else:
        return False




x_y = defaultdict(lambda:set())
for _ in range(m):
    x, y = map(int, input().split())
    x_y[x].add(y)
    x_y[y].add(x)



count = 0
for index in range(len(p)):
    start = index + 1
    to = p[index]
    used = []
    if dp(start, to, used):
        # 交換可能
        count += 1
print(count)

Buggy submission (verdict: Runtime Error):

from collections import defaultdict



n, m = map(int, input().split())
p = list(map(int, input().split()))

def dp(start, to, used):
    if start == to:
        return True
    if start in x_y:
        is_ok = False
        for next_start in x_y[start]:
            if not next_start in used:
                #remove used
                used.append(next_start)
                if dp(next_start, to, used):
                    return True
        return is_ok

    else:
        return False




x_y = defaultdict(lambda:set())
for _ in range(m):
    x, y = map(int, input().split())
    x_y[x].add(y)
    x_y[y].add(x)


count = 0
for index in range(len(p)):
    start = index + 1
    to = p[index]
    used = []
    if dp(start, to, used):
        # 交換可能
        count += 1
print(count)

Buggy submission (verdict: Runtime Error):

from collections import defaultdict



n, m = map(int, input().split())
p = list(map(int, input().split()))

def dp(start, to, used):
    if start == to:
        return True
    if start in x_y:
        is_ok = False
        for next_start in x_y[start]:
            if not next_start in used:
                #remove used
                used.append(next_start)
                if dp(next_start, to, used):
                    return True
        return is_ok

    else:
        return False




x_y = defaultdict(lambda:set())
for _ in range(m):
    x, y = map(int, input().split())
    x_y[x].add(y)
    x_y[y].add(x)


count = 0
for index in range(len(p)):
    start = index + 1
    to = p[index]
    used = []
    if dp(start, to, used):
        # 交換可能
        p[start-1] ,p[to -1] = p[to -1] ,p[start -1] 
        count += 1
print(count)