Problem:


Score : 600 points

Problem Statement

There are N dots in a two-dimensional plane. The coordinates of the i-th dot are (x_i, y_i).

We will repeat the following operation as long as possible:

Choose four integers a, b, c, d (a \neq c, b \neq d) such that there are dots at exactly three of the positions (a, b), (a, d), (c, b) and (c, d), and add a dot at the remaining position.

We can prove that we can only do this operation a finite number of times. Find the maximum number of times we can do the operation.

Constraints

1 \leq N \leq 10^5

1 \leq x_i, y_i \leq 10^5

If i \neq j, x_i \neq x_j or y_i \neq y_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the maximum number of times we can do the operation.

Sample Input 1

3
1 1
5 1
5 5

Sample Output 1

1

By choosing a = 1, b = 1, c = 5, d = 5, we can add a dot at (1, 5). We cannot do the operation any more, so the maximum number of operations is 1.

Sample Input 2

2
10 10
20 20

Sample Output 2

0

There are only two dots, so we cannot do the operation at all.

Sample Input 3

9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5

Sample Output 3

16

We can do the operation for all choices of the form a = 1, b = 1, c = i, d = j (2 \leq i,j \leq 5), and no more. Thus, the maximum number of operations is 16.



Sample input:
3
1 1
5 1
5 5


Sample output:
1

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    for i in range(3):
        if s[i] == s[i + 1]:
            print("Bad")
            return
    print("Good")
    return

#B
def B():
    n, l = LI()
    lis = [l + i for i in range(n)]
    s = sum(lis)
    a = inf
    for i in lis:
        if abs(a) > abs(i):
            a = i
    print(s-a)
    return

#C
def C():
    def gcd(a, b):
        a, b = max(a, b), min(a, b)
        while b:
            a, b = b, a % b
        return a
    def lcm(a, b):
        return a * b // gcd(a, b)
    a, b, c, d = LI()
    x = b // c - (a-1) // c
    y = b // d - (a-1) // d
    z = b // lcm(c , d) - (a-1) // lcm(c , d)
    print(b-a+1-(x+y-z))
    return

#D
def D():
    n = II()
    ab = LIR(n)
    ab.sort(key=lambda x: x[1])
    now = 0
    for a, b in ab:
        now += a
        if now <= b:
            continue
        print("No")
        return
    print("Yes")
    return

#E
def E():
    n, k = LI()
    if k > (n - 1) * (n - 2) / 2:
        print(-1)
        return
    d = (n - 1) * (n - 2) // 2 - k
    a = [[] for i in range(n)]
    for i in range(n):
        if i != 1:
            a[i].append(1)
            a[1].append(i)
    l = 0
    m = 2
    while d > 0:
        a[l].append(m)
        m += 1
        d -= 1
        if m == n:
            l += 1
            m = l + 1
            if l == 1:
                l = 2
                m = 3
    aa = 0
    ans = []
    for num,i in enumerate(a):
        for l in i:
            if num < l:
                aa += 1
                ans.append((num+1,l+1))
    print(aa)
    for x, y in ans:
        print(x, y)
    return

#F
def F():
    n = II()
    xy = LIR(n)
    d = defaultdict(list)
    par = defaultdict(int)
    for _, y in xy:
        par[y] = y
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return False
        if x > y: x, y = y, x
        par[y] = x
        return True
    
    setx = set()
    for x, y in xy:
        d[x].append(y)
    for key, value in d.items():
        p = value[0]
        for v in value[1:]:
            unite(p, v)
    ans1 = defaultdict(int)
    ans2 = defaultdict(int)
    ans = 0
    for x, y in xy:
        root(y)
    # print(par)
    for _, value in d.items():
        ans1[par[value[0]]] += 1
    for _, value in par.items():
        ans2[value] += 1
    # print(ans1,ans2)
    for key, value in ans1.items():
        ans += ans2[key] * value
    print(ans - n)
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

import sys
input=sys.stdin.readline
n=int(input())
UF=UF(2*10**5)
for i in range(n):
  x,y=map(int,input().split())
  UF.unite(x-1+10**5,y-1)
UF.groupnum()
ct=[[0,0] for i in range(2*10**5)]
for i in range(2*10**5):
  if i<10**5:
    ct[UF._parent[i]][0]+=1
  else:
    ct[UF._parent[i]][1]+=1
ans=0
for i in range(2*10**5):
  ans+=ct[i][0]*ct[i][1]
print(ans-n)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.size = [1 for _ in range(size)]

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

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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y]+=self.size[x]
        else:
            self.parent[y] = x
            self.size[x]+=self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
      
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]



N = int(input())
U = UnionFind(N)
xyi = []
xy = []
for i in range(N):
    x, y = map(int, input().split())
    xyi.append((x, y, i))
    xy.append((x, y))
xyi.sort()
for j in range(N-1):
    x0, y0, i0 = xyi[j]
    x1, y1, i1 = xyi[j+1]
    if x0 == x1:
        U.unite(i0, i1)
xyi.sort(key = lambda x:x[1])
for j in range(N-1):
    x0, y0, i0 = xyi[j]
    x1, y1, i1 = xyi[j+1]
    if y0 == y1:
        U.unite(i0, i1)
equiv = [[set(), set()] for _ in range(N)]
for i in range(N):
    p = U.find(i)
    equiv[p][0].add(xy[i][0])
    equiv[p][1].add(xy[i][1])
ans = 0
for i in range(N):
    ans+=len(equiv[i][0])*len(equiv[i][1])
ans-=N
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]

    MAX = 10**5
    Xs = [[] for _ in range(MAX+1)]
    Ys = [[] for _ in range(MAX+1)]
    for i, (x, y) in enumerate(XY):
        Xs[x].append(i)
        Ys[y].append(i)

    ans = 0
    checked = [False]*N
    for i in range(N):
        if checked[i]: continue
        q = [i]
        checked[i] = True
        X = set()
        Y = set()
        c = 0
        while q:
            qq = []
            for p in q:
                x, y = XY[p]
                X.add(x)
                Y.add(y)
                c += 1
                for ni in Xs[x]:
                    if not checked[ni]:
                        checked[ni] = True
                        qq.append(ni)
                for ni in Ys[y]:
                    if not checked[ni]:
                        checked[ni] = True
                        qq.append(ni)
            q = qq
        ans += len(X)*len(Y)-c

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.rank = [0] * n
		self.size = [1] * n

	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_check(self, x, y):
		return self.find(x) == self.find(y)

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			if self.same_check(x, y) != True:
				self.size[y] += self.size[x]
				self.size[x] = 0
			self.par[x] = y
		else:
			if self.same_check(x, y) != True:
				self.size[x] += self.size[y]
				self.size[y] = 0
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def siz(self, x):
		x = self.find(x)
		return self.size[x]

#処理内容
def main():
	N = int(input())
	Lx = []
	Ly = []
	UF = UnionFind(N)
	for i in range(N):
		x, y = getlist()
		Lx.append([x, y, i])
		Ly.append([y, x, i])
	Lx = sorted(Lx)
	Ly = sorted(Ly)
	for i in range(N - 1):
		if Lx[i][0] == Lx[i + 1][0]:
			UF.union(Lx[i][2] , Lx[i + 1][2])
		if Ly[i][0] == Ly[i + 1][0]:
			UF.union(Ly[i][2] , Ly[i + 1][2])
	for i in range(N):
		UF.par[i] = UF.find(i)

	nodeX = [[] for i in range(N)] 
	nodeY = [[] for i in range(N)]
	PAR = UF.par
	for i in range(N):
		nodeX[PAR[Lx[i][2]]].append(Lx[i][0])
		nodeY[PAR[Lx[i][2]]].append(Lx[i][1])
	# print(nodeX)
	# print(nodeY)

	#計算
	ans = 0
	D = defaultdict(int)
	for i in range(N):
		if D[PAR[i]] == 0:
			D[PAR[i]] = 1
			ans += len(set(nodeX[PAR[i]])) * len(set(nodeY[PAR[i]])) - UF.size[PAR[i]]
	print(ans) 



if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1



U = UnionFind(10 ** 5 * 2)
n = I()
X = []
Y = []
for _ in range(n):
    x, y = LI()
    U.union(x - 1, y - 1 + 10 ** 5)


XD = defaultdict(int)
YD = defaultdict(int)
for i in range(10 ** 5 * 2):
    if i < 10 ** 5:
        XD[U.root(i)] += 1
    else:
        YD[U.root(i)] += 1


ret = 0
for j in range(10 ** 5 * 2):
    ret += XD[j] * YD[j]


print(ret - n)

Submission status: Accepted

Solution code:
import copy
import collections
import sys
read = sys.stdin.read
NXY = [int(_) for _ in read().split()]
N = NXY[0]
X = NXY[1::2]
Y = NXY[2::2]
xi = {x: i for i, x in enumerate(set(X))}
yj = {y: j for j, y in enumerate(set(Y))}


class UnionFind():
    def __init__(self, size):
        self.dat = list(range(size))
        self.SIZE = [1] * size  # 0-indexed

    def find(self, x):
        dat = self.dat
        stack = [x]
        while True:
            y = stack[-1]
            if dat[y] != y:
                stack += [dat[y]]
            else:
                break
        for s in stack:
            dat[s] = y
        return y

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        dat = self.dat
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = dat[X] = Y
            else:
                m = dat[Y] = X
            SIZE[m] = SX + SY
            SIZE[X + Y - m] = 0

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

    def scan_uf(self):
        find = self.find
        length = len(self.dat)
        for i in range(length):
            find(i)

    def size(self, x):
        return self.SIZE[self.find(x)]


ufx = UnionFind(len(xi))
ufy = UnionFind(len(yj))
sxy = collections.defaultdict(set)
syx = collections.defaultdict(set)
for x, y in zip(X, Y):
    i = xi[x]
    j = yj[y]
    sxy[i].add(j)
    syx[j].add(i)
sxy2 = copy.deepcopy(sxy)
for sy in sxy.values():
    y1 = sy.pop()
    for y in sy:
        ufy.unite(y1, y)
for sx in syx.values():
    x1 = sx.pop()
    for x in sx:
        ufx.unite(x1, x)
ufx.scan_uf()
ufy.scan_uf()
ans = 0
for x, vx in enumerate(ufx.SIZE):
    if vx:
        vy = ufy.size(sxy2[x].pop())
        ans += vx * vy
print(ans - N)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1



n = I()
U = UnionFind(10 ** 5 * 2)
for i in range(n):
    x, y = LI()
    U.union(x - 1, y + 10 ** 5 - 1)



X = [0] * 10 ** 5 * 2
Y = [0] * 10 ** 5 * 2
for x in range(10 ** 5):
    X[U.root(x)] += 1
for y in range(10 ** 5, 10 ** 5 * 2):
    Y[U.root(y)] += 1


ret = 0
for j in range(10 ** 5 * 2):
    ret += X[j] * Y[j]


print(ret - n)

Submission status: Accepted

Solution code:
def main():
    MAX = 10 ** 5 + 1

    data = [-1] * (2 * MAX)

    def find(x):
        if data[x] < 0:
            return x
        else:
            data[x] = find(data[x])
            return data[x]

    def union(x, y):
        x, y = find(x), find(y)
        if x != y:
            if data[y] < data[x]:
                x, y = y, x
            data[x] += data[y]
            data[y] = x
        return (x != y)


    N, *XY = map(int, open(0).read().split())

    for x, y in zip(*[iter(XY)] * 2):
        union(x, y + MAX)

    X = [0] * (MAX * 2)
    Y = [0] * (MAX * 2)

    for i in range(MAX):
        X[find(i)] += 1
    for i in range(MAX, MAX * 2):
        Y[find(i)] += 1

    res = sum(X[i] * Y[i] for i in range(MAX * 2))

    print(res - N)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    MAX = 10 ** 5 + 1

    data = [-1] * (2 * MAX)

    def find(x):
        if data[x] < 0:
            return x
        else:
            data[x] = find(data[x])
            return data[x]

    def union(x, y):
        x, y = find(x), find(y)
        if x != y:
            if data[y] < data[x]:
                x, y = y, x
            data[x] += data[y]
            data[y] = x
        return (x != y)


    N, *XY = map(int, open(0).read().split())

    for x, y in zip(*[iter(XY)] * 2):
        union(x, y + MAX)

    X = Counter(find(i) for i in range(MAX))
    Y = Counter(find(i) for i in range(MAX, MAX * 2))
    res = sum(X[i] * Y[i] for i in range(MAX * 2))

    print(res - N)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    class UnionFind:
        def __init__(self, size):
            self.data = [-1] * size

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

        def union(self, x, y):
            x, y = self.find(x), self.find(y)
            if x != y:
                if self.data[y] < self.data[x]:
                    x, y = y, x
                self.data[x] += self.data[y]
                self.data[y] = x
            return (x != y)

    MAX = 10 ** 5 + 1
    uf = UnionFind(2 * MAX)

    N, *XY = map(int, open(0).read().split())

    for x, y in zip(*[iter(XY)] * 2):
        uf.union(x, y + MAX)

    X = Counter(uf.find(i) for i in range(MAX))
    Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
    res = sum(X[i] * Y[i] for i in range(MAX * 2))

    print(res - N)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


def main():
    MAX = 10 ** 5 + 1
    uf = UnionFind(2 * MAX)

    N, *XY = map(int, open(0).read().split())

    for x, y in zip(*[iter(XY)] * 2):
        uf.union(x, y + MAX)

    X = Counter(uf.find(i) for i in range(MAX))
    Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
    res = sum(X[i] * Y[i] for i in range(MAX * 2))

    print(res - N)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


MAX = 10 ** 5 + 10
uf = UnionFind(2 * MAX)

N, *XY = map(int, open(0).read().split())

for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y + MAX)

X = Counter(uf.find(i) for i in range(MAX))
Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
res = sum(X[i] * Y[i] for i in range(MAX * 2))

print(res - N)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

"""
点(x,y) を、辺x-yと見て二部グラフとみなす
"""

N = int(readline())
XY = np.array(read().split(),np.int32)

U = 10**5 + 100
X = XY[::2]; Y = XY[1::2]
graph = csr_matrix((np.ones(N),(X,Y+U)),(U+U,U+U))
Ncomp,comp = connected_components(graph)

comp_x=np.bincount(comp[:U],minlength=Ncomp) # 連結成分に含まれるx座標の個数
comp_y=np.bincount(comp[U:],minlength=Ncomp) # 連結成分に含まれるx座標の個数
comp_E=np.bincount(comp[X],minlength=Ncomp) # 連結成分に含まれる辺の個数

answer = (comp_x * comp_y - comp_E).sum()
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

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


def main():
    N = int(input())
    xy_list = []
    x_list = []
    y_list = []
    for i in range(N):
        x, y = map(int, input().split())
        xy_list.append((x, y))
        x_list.append(x)
        y_list.append(y)

    x_list = list(set(x_list))
    y_list = list(set(y_list))
    x_list.sort()
    y_list.sort()
    dictX = {}
    dictY = {}
    for i, x in enumerate(x_list):
        dictX[x] = i
    for i, y in enumerate(y_list):
        dictY[y] = i

    xy_c = [[] for _ in range(len(x_list))]
    for x, y in xy_list:
        xc, yc = dictX[x], dictY[y]
        xy_c[xc].append(yc)

    UF = UnionFind(len(y_list) + 1)
    for i in range(len(x_list)):
        j_list = xy_c[i]
        if len(j_list) > 1:
            j0 = j_list[0]
            for j in j_list[1:]:
                UF.unite(j0, j)

    ans = 0
    for i in range(len(x_list)):
        j0 = xy_c[i][0]
        ans += UF.size(j0) - len(xy_c[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, = [int(x) for x in input().split(" ")]
dx = [set() for x in range(10**5+1)]
dy = [set() for x in range(10**5+1)]

class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1
        self.x_num = 0

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.member_num_ = root.member_num_ + unite_root.member_num_
                root.x_num = max(root.x_num, unite_root.x_num)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.member_num_ = root.member_num_ + unite_root.member_num_
                unite_root.x_num = max(root.x_num, unite_root.x_num)

for i in range(n):
    x, y = [int(x) for x in input().split(" ")]
    dx[x].add(y)
    dy[y].add(x)

node_list = [UnionFindNode(i) for i in range(len(dy))]

for xi, dxx in enumerate(dx):
    b = None
    for y in dxx:
        if b == None:
            b = y
            continue
        node_list[y].unite(node_list[b])
        b = y

r = 0
for xi, dxx in enumerate(dx):
    if len(dxx) == 0:
        continue
    r += node_list[dxx.pop()].root().member_num_ 

print(r-n)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import queue

n = int(sys.stdin.readline())

graph = defaultdict(list)

X, Y = [[] for i in range(n)], [[] for i in range(n)]
atX, atY = defaultdict(list), defaultdict(list)

for i in range(n):
	a, b = map(int, sys.stdin.readline().split())
	a -= 1; b-= 1
	X[i] = a; Y[i] = b
	atX[X[i]].append(i)
	atY[Y[i]].append(i)

visX = set(); visY = set()
found = [False]*n

ans = n*(-1)
for root in range(n):
	if found[root]: continue
	usedX, usedY = set(), set()

	que = queue.Queue()
	que.put(root)
	found[root] = True
	usedX.add(X[root])
	usedY.add(Y[root])

	while not que.empty():
		cur = que.get()
		toVisit = []
		if X[cur] not in visX:
			visX.add(X[cur])
			for ele in atX[X[cur]]:
				toVisit.append(ele)
		if Y[cur] not in visY:
			visY.add(Y[cur])
			for ele in atY[Y[cur]]:
				toVisit.append(ele)

		for ele in toVisit:
			if found[ele]: continue
			found[ele] = True
			usedX.add(X[ele])
			usedY.add(Y[ele])
			que.put(ele)
	ans += len(usedX)*len(usedY)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
adj = [[] for _ in range(200000)]
for x, y in p:
	adj[x-1].append(y+99999)
	adj[y+99999].append(x-1)

visited = [False for _ in range(200000)]

def dfs(orig):
	stack = [orig]
	edges = len(adj[orig])
	if orig < 100000:
		x_num, y_num = 1, 0
	else:
		x_num, y_num = 0, 1

	while stack:
		v = stack.pop()
		for w in adj[v]:
			if visited[w] == False:
				visited[w] = True
				if w < 100000:
					x_num += 1
				else:
					y_num += 1
				edges += len(adj[w])
				stack.append(w)
	return x_num * y_num - (edges // 2)

ans = 0
for i in range(200000):
	if visited[i] == False and adj[i]:
		visited[i] = True
		ans += dfs(i)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

m = 10**5

edge = [[] for i in range(2*m)]

for i in range(n):
    x,y = map(int,input().split())
    x -= 1
    y -= 1 
    y += m
    edge[x].append(y)
    edge[y].append(x)

used = [False]*2*m

res = 0

for e in range(m):
    if used[e]:
        continue
    used[e] = True
    tank = []
    new = [e]

    px = 0
    py = 0

    if e >= 10**5:
        py += 1
    else:
        px += 1

    while len(new) > 0:
        tank = []
        for fr in new:
            for go in edge[fr]:
                if not used[go]:
                    tank.append(go)
                    used[go] = True
                    if go >= 10**5:
                        py += 1
                    else:
                        px += 1

        new = tank
    
    res += px*py
print(res-n)

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import defaultdict
import sys
input = sys.stdin.readline

# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

UF = UnionFind(N)
for k in range(2):
    xys.sort(key=itemgetter(k))
    for i in range(N-1):
        if xys[i][k] == xys[i+1][k]:
            UF.union(xys[i][2], xys[i+1][2])

Xs = defaultdict(set)
Ys = defaultdict(set)
for x, y, i in xys:
    no = UF.find(i)
    Xs[no].add(x)
    Ys[no].add(y)

ans = 0
for no in Xs.keys():
    ans += len(Xs[no]) * len(Ys[no])

print(ans - N)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
xys = [tuple(map(int, input().split())) for _ in range(N)]

M = 10**5
UF = UnionFind(2*M)
for x, y in xys:
    x, y = x-1, y-1
    UF.union(x, y+M)

for x in range(2*M):
    UF.find(x)

cntX = Counter(UF.pars[:M])
cntY = Counter(UF.pars[M:])

ans = 0
for v in cntX.keys():
    ans += cntX[v] * cntY[v]

print(ans - N)