Problem:


Problem D: King Slime

There is a grid of size W &times; H surrounded by walls. Some cells in the grid are occupied by slimes. The slimes want to unite with each other and become a "King Slime".

In each move, a slime can move to east, west, south and north direction until it enters a cell occupied by another slime or hit the surrounding wall. If two slimes come together, they unite and become a new slime.

Your task is write a program which calculates the minimum number of moves that all the slimes unite and become a King Slime. Suppose slimes move one by one and they never move simultaneously.

Input

The first line contains three integers N (2 ≤ N ≤ 40,000), W and H (1 ≤ W, H ≤ 100,000), which denote the
number of slimes, the width and the height of the grid respectively.

The following N lines describe the initial coordinates of the slimes. The i-th line contains two integers xi (1 ≤ xi ≤ W) and yi (1 ≤ yi ≤ H), which indicate the coordinates of the i-th slime . All the coordinates are 1-based.

You may assume that each cell is occupied by at most one slime initially.

Output

Output the minimum number of moves that all the slimes unite and become a King Slime.

Sample Input 1

4 3 3
1 1
1 3
3 1
3 3

Output for the Sample Input 1

3

Sample Input 2

2 3 3
2 2
3 3

Output for the Sample Input 2

2

Sample Input 3

2 4 4
2 2
3 3

Output for the Sample Input 3

3

Sample Input 4

2 4 4
2 2
2 3

Output for the Sample Input 4

1



Sample input:
4 3 3
1 1
1 3
3 1
3 3


Sample output:
3

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

N, H, W = map(int, raw_input().split())

E = [[] for i in range(N)]
lst = []
flag = True

for i in range(N):
    x, y = map(int, raw_input().split())
    if x == 1 or y == 1 or x == W or y == H:
        flag = False
    lst.append((x, y, i))

lst.sort()

for i in range(N):
    if i + 1 != N and lst[i][0] == lst[i + 1][0]:
        E[lst[i][2]].append(lst[i + 1][2])
        E[lst[i + 1][2]].append(lst[i][2])
    if lst[i][0] == lst[i - 1][0]:
        E[lst[i][2]].append(lst[i - 1][2])
        E[lst[i - 1][2]].append(lst[i][2])

lst2 = []

for i in range(N):
    x, y, index = lst[i]
    lst2.append((y, x, index))

lst = lst2
lst.sort()

for i in range(N):
    if i + 1 != N and lst[i][0] == lst[i + 1][0]:
        E[lst[i][2]].append(lst[i + 1][2])
        E[lst[i + 1][2]].append(lst[i][2])
    if lst[i][0] == lst[i - 1][0]:
        E[lst[i][2]].append(lst[i - 1][2])
        E[lst[i - 1][2]].append(lst[i][2])

used = [False for i in range(N)]

def func(num, pre):
    if used[num]:
        return
    used[num] = True
    for to in E[num]:
        if to != pre:
            func(to, num)

#print E

cnt = 0

for i in range(N):
    if not used[i]:
        func(i, -1)
        cnt += 1

if cnt > 1 and flag:
    cnt += 1
print N - 2 + cnt

Submission status: Accepted

Solution code:
import sys

class UnionFind:
    def __init__(self,sz):
        self.__ranks = [1] * sz
        self.__parents = [ i for i in range(sz) ]
    def find_parent(self, x):
        if x == self.__parents[x]:
            return x
        else:
            self.__parents[x] = self.find_parent(self.__parents[x])
            return self.__parents[x]
    def same(self, x, y):
        return self.find_parent(x) == self.find_parent(y)
    def unite(self, x, y):
        px = self.find_parent(x)
        py = self.find_parent(y)
        if px == py:
            return
        if self.__ranks[px] > self.__ranks[py]:
            self.__parents[py] = px
        else:
            self.__parents[px] = py
            if self.__ranks[px] == self.__ranks[py]:
                self.__ranks[py] += 1

def main():
    n,w,h = map(int, input().split())

    uf = UnionFind(n)
    xd = {}
    yd = {}
    is_edges_slime = False
    for i in range(n):
        x,y = map(int, sys.stdin.readline().split())

        if x == 1 or x == w:
            is_edges_slime = True
        if y == 1 or y == h:
            is_edges_slime = True

        if x in xd:
            uf.unite(xd[x], i)
        else:
            xd[x] = i
        
        if y in yd:
            uf.unite(yd[y], i)
        else:
            yd[y] = i

    root = set()
    for i in range(n):
        root.add( uf.find_parent(i) )

    if len(root) == 1:
        print(n - 1)
    else:
        ans = n - len(root) # ????´?????????¨??????
        ans += len(root) - (1 if is_edges_slime else 0) # ???????????????
        ans += len(root) - 1 # ????????°???????????????
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

N, W, H = map(int, raw_input().split())

E = [[] for i in range(N)]
lst = []
flag = True

for i in range(N):
    x, y = map(int, raw_input().split())
    if x == 1 or y == 1 or x == W or y == H:
        flag = False
    lst.append((x, y, i))

lst.sort()
for i in range(N):
    if lst[i][0] == lst[i - 1][0]:
        E[lst[i][2]].append(lst[i - 1][2])
        E[lst[i - 1][2]].append(lst[i][2])

lst2 = []

for i in range(N):
    x, y, index = lst[i]
    lst2.append((y, x, index))

lst = lst2
lst.sort()
for i in range(N):
    if lst[i][0] == lst[i - 1][0]:
        E[lst[i][2]].append(lst[i - 1][2])
        E[lst[i - 1][2]].append(lst[i][2])

used = [False for i in range(N)]

def func(num, pre):
    if used[num]:
        return
    used[num] = True
    for to in E[num]:
        if to != pre:
            func(to, num)

#print E

cnt = 0

for i in range(N):
    if not used[i]:
        func(i, -1)
        cnt += 1

if cnt > 1 and flag:
    cnt += 1
print N - 2 + cnt

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

N, W, H = map(int, raw_input().split())

E = [[] for i in range(N)]
lst = []
flag = True

for i in range(N):
    x, y = map(int, raw_input().split())
    if x == 1 or y == 1 or x == W or y == H:
        flag = False
    lst.append((x, y, i))

lst.sort()
for i in range(N):
    if lst[i][0] == lst[i - 1][0]:
        E[lst[i][2]].append(lst[i - 1][2])
        E[lst[i - 1][2]].append(lst[i][2])

lst2 = []

for i in range(N):
    x, y, index = lst[i]
    lst2.append((y, x, index))

lst = lst2
lst.sort()
for i in range(N):
    if lst[i][0] == lst[i - 1][0]:
        E[lst[i][2]].append(lst[i - 1][2])
        E[lst[i - 1][2]].append(lst[i][2])

used = [False for i in range(N)]

def func(num, pre):
    if used[num]:
        return
    used[num] = True
    for to in E[num]:
        if to != pre:
            func(to, num)

cnt = 0

for i in range(N):
    if not used[i]:
        func(i, -1)
        cnt += 1

if cnt > 1 and flag:
    cnt += 1
print N - 2 + cnt

Submission status: Accepted

Solution code:

N, W, H = map(int, raw_input().split())

E = [[] for i in range(N)]
lst = []
flag = True

for i in range(N):
    x, y = map(int, raw_input().split())
    if x == 1 or y == 1 or x == W or y == H:
        flag = False
    lst.append((x, y, i))

lst.sort()
for i in range(N):
    if lst[i][0] == lst[i - 1][0]:
        E[lst[i][2]].append(lst[i - 1][2])
        E[lst[i - 1][2]].append(lst[i][2])

lst2 = []

for i in range(N):
    x, y, index = lst[i]
    lst2.append((y, x, index))

lst = lst2
lst.sort()
for i in range(N):
    if lst[i][0] == lst[i - 1][0]:
        E[lst[i][2]].append(lst[i - 1][2])
        E[lst[i - 1][2]].append(lst[i][2])

used = [False for i in range(N)]

def func(num, pre):
    if used[num]:
        return
    used[num] = True
    for to in E[num]:
        if to != pre:
            func(to, num)

cnt = 0

for i in range(N):
    if not used[i]:
        func(i, -1)
        cnt += 1

if cnt > 1 and flag:
    cnt += 1
print N - 2 + cnt

Submission status: Accepted

Solution code:
from collections import defaultdict
N, W, H = map(int, input().split())

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        p[py] = px
    else:
        p[px] = py

X = defaultdict(list)
Y = defaultdict(list)
for i in range(N):
    x, y = map(int, input().split())
    X[x].append(i)
    Y[y].append(i)

for x, vs in X.items():
    prv = vs[0]
    for v in vs[1:]:
        unite(prv, v)
        prv = v
for y, vs in Y.items():
    prv = vs[0]
    for v in vs[1:]:
        unite(prv, v)
        prv = v

cnt = 0
for i in range(N):
    pt = root(i)
    if pt == i:
        cnt += 1
ans = N-cnt + 2*(cnt-1)
if cnt > 1 and 1 not in X and W not in X and 1 not in Y and H not in Y:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.data=[-1 for i in range(n)]

    def root(self,x):
        if self.data[x]<0:
            return x
        else:
            self.data[x]=self.root(self.data[x])
            return self.data[x]

    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.data[y]<self.data[x]:
            x,y=y,x
        self.data[x]+= self.data[y]
        self.data[y] = x

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

    def size(self,x):
        return -self.data[self.root(x)]

n,w,h=map(int,input().split())
slime_w = [[]for i in range(w)]
slime_h = [[]for i in range(h)]
uf=UnionFind(n)
f=False
for i in range(n):
    x,y=map(int,input().split())
    if x==1 or y==1 or x==w or y==h:
        f=True
    x,y=x-1,y-1
    slime_w[x].append(i)
    slime_h[y].append(i)
for i in range(h):
    if len(slime_h[i])>1:
        p=slime_h[i][0]
    for j in range(1,len(slime_h[i])):
        uf.uni(p,slime_h[i][j])
for i in range(w):
    if len(slime_w[i])>1:
        p=slime_w[i][0]
    for j in range(1,len(slime_w[i])):
        uf.uni(p,slime_w[i][j])
count=[-e-1 for e in uf.data if e<0]
if f:
    print(sum(count)+(len(count)-1+len(count)-1 if len(count)!=1 else 0))
else:
    print(sum(count)+(len(count)+len(count)-1 if len(count)!=1 else 0))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    rr = []

    def f(n,w,h):
        wd = {}
        hd = {}
        kf = 0
        uf = UnionFind(n+1)
        uc = 0
        for i in range(n):
            x,y = LI()
            if x in wd:
                if uf.union(wd[x], i):
                    uc += 1
            else:
                wd[x] = i
            if y in hd:
                if uf.union(hd[y], i):
                    uc += 1
            else:
                hd[y] = i
            if x == 1 or y == 1 or x == w or y == h:
                kf = 1
        r = uc
        nk = n - uc
        if nk == 1:
            return r
        r += nk - kf + nk - 1

        return r

    while 1:
        n,w,h = LI()
        if n == 0:
            break
        rr.append(f(n,w,h))
        # print(n, rr[-1])
        break

    return '\n'.join(map(str, rr))


print(main())