Submission #35656907

---

Source Code Expand

def D(N, XY):
    contain = [[-1] * 20010 for _ in range(2010)]
    for i, (x, y) in enumerate(XY):
        contain[x+1005][y+1005] = i
        
    dsu = [-1] * N
    def leader(i):
        if dsu[i] < 0: return i
        dsu[i] = leader(dsu[i])
        return dsu[i]
    
    def merge(i, j):
        '''サイズの大きい方(x)に小さい方(y)をマージ'''
        if i == j: return
        x = leader(i)
        y = leader(j)
        if x == y: return
        
        if dsu[x] > dsu[y]: x, y = y, x
        
        dsu[x] += dsu[y]
        dsu[y] = x
        
    def get_neighbors(i, j):
        return (
            [i-1,j-1],
            [i-1,j],
            [i,j-1],
            [i,j+1],
            [i+1,j],
            [i+1,j+1],
        )
    
    for i, (x, y) in enumerate(XY):
        for s, t in get_neighbors(x, y):
            idx = contain[s+1005][t+1005]
            if idx > -1:
                merge(i, idx)
                
    return sum(1 for n in dsu if n < 0)
        
# 提出用
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
 
print(D(N, XY))

Submission Info

Judge Result