Problem: We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N. We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M). AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i = i is maximized:    * Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.  Find the maximum possible number of i such that p_i = i after operations.

Submission attempts (in order):


class Board:

    
    
    
    h = {}
    m = {}

    island = 0  

    
    def add(self, h, new_item):
        self.h[new_item] = h

    
    def merge(self, h1, h2):
        self.m[h2] = self.m[h1]

    
    def new_pair(self, x, y):
        new_h = len(self.m) + 1
        self.island += 1

        self.h[x] = new_h
        self.h[y] = new_h
        self.m[new_h] = self.island

    
    def add_pair(self, x, y):
        
        if x in self.h:
            h_x = self.h[x]
            if y in self.h:
                h_y = self.h[y]
                if self.m[h_x] == self.m[h_y]:
                    pass
                else:
                    self.merge(h_x, h_y)
            else:
                self.add(h_x, y)
        else:
            if y in self.h:
                self.add(self.h[y], x)
            else:
                self.new_pair(x, y)

    
    def movable(self, i, j):
        return i == j \
               or (i in self.h and j in self.h and self.m[self.h[i]] == self.m[self.h[j]])

    def equals(self, *tips):
        result = 0

        for i, x in enumerate(tips):
            if self.movable(i, x):
                result += 1

        return result


def main():
    n, m = map(int, input().split())
    tips = map(int, input().split())
    board = Board()
    for i in range(m):
        pair = map(int, input().split())
        board.add_pair(*pair)
    print("{0:d}".format(board.equals(*tips)))


main()


class Elements:
    s = set()

    def __init__(self, *elements):
        self.s = set(elements)

    def add(self, x):
        self.s.add(x)

    def remove(self, x):
        self.s.remove(x)

    def union(self, e):
        self.s |= e.s


class Hoge:
    h = {}
    elements_set = set()

    def add(self, at, new_item):
        self.h[at].add(new_item)
        self.h[new_item] = self.h[at]

    def union(self, x, y):
        if len(self.h[y].s) > len(self.h[x].s):
            x, y = y, x

        self.h[x].union(self.h[y])
        self.elements_set.remove(self.h[y])
        for i in self.h[y].s:
            self.h[i] = self.h[x]

    def new_pair(self, x, y):
        u = Elements(x, y)
        self.h[x] = u
        self.h[y] = u
        self.elements_set.add(u)

    def add_pair(self, x, y):
        if x in self.h:
            if y in self.h:
                if self.h[x] is self.h[y]:
                    pass
                else:
                    self.union(x, y)
            else:
                self.add(x, y)
        else:
            if y in self.h:
                self.add(y, x)
            else:
                self.new_pair(x, y)

    def equals(self, *l):
        result = 0

        
        for i, x in enumerate(l):
            if i == x and x not in self.h:
                result += 1

        
        for es in self.elements_set:
            s = es.s
            for x in s:
                if l[x] in s:
                    result += 1

        return result


def main():
    n, m = map(int, input().split())
    l = map(lambda s: int(s)-1, input().split())
    hoge = Hoge()
    for i in range(1, m + 1):
       pair = map(lambda s: int(s)-1, input().split())
       hoge.add_pair(*pair)
    print("{0:d}".format(hoge.equals(*l)))


main()


Verdicts: Wrong Answer

Accepted