Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



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


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n

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

    def size(self, a):
        return -self.parent[self.root(a)]

    def connect(self, a, b) -> bool:
        a = self.root(a)
        b = self.root(b)

        if a == b:
            return False

        if self.size(a) < self.size(b):
            a, b = b, a

        self.parent[a] += self.parent[b]

        self.parent[b] = a

        return True


N, M, K = map(int, input().split())
fri_g = dict([str(i), []] for i in range(N))
blk_g = dict([str(i), []] for i in range(N))
unif = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    unif.connect(a-1, b-1)
    fri_g[str(a-1)].append(b-1)
    fri_g[str(b-1)].append(a-1)

for _ in range(K):
    c, d = map(int, input().split())
    blk_g[str(c-1)].append(d-1)
    blk_g[str(d-1)].append(c-1)

for i in range(N):
    i_str = str(i)
    n_link = unif.size(i) - 1  # remove theirselves
    n_friends = len(fri_g[i_str])
    n_blk_and_link = sum([unif.root(d) == unif.root(i) for d in blk_g[i_str]])
    # n_blk_and_link = 0
    # for d in blk_g[i_str]:
    #     n_blk_and_link += unif.root(d) == unif.root(i)

    print(n_link - n_friends - n_blk_and_link)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] > self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.par[x] = y
            self.size[y] += self.size[x]

    def same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


n,m,k=map(int,input().split())
tomo=[[] for _ in range(n)]
blo=[[] for _ in range(n)]
tomouf=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tomo[a].append(b)
    tomo[b].append(a)
    tomouf.union(a,b)
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    blo[a].append(b)
    blo[b].append(a)
aans=[]
for i in range(n):
    ans=tomouf.get_size(i)
    for j in tomo[i]:
        if tomouf.same(i,j):
            ans-=1
    for j in blo[i]:
        if tomouf.same(i,j):
            ans-=1
    aans.append(ans-1)
print(*aans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friend = [0] * (n+1)
block = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    friend[a] += 1
    friend[b] += 1
    uf.union(a-1, b-1)

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        block[c] += 1
        block[d] += 1

w = [0] * (n+1)

for i in range(1, n+1):
    w[i] = uf.size(i-1) - friend[i] - block[i] - 1

print(*w[1:])

Submission status: Accepted

Solution code:
class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -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]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			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 Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)

N, M, K = map(int, input().split())

solve = UnionFind(N)
cntF = [0] * (N)

for _ in range(M):
	ta,tb = map(int, input().split())
	ta -= 1
	tb -= 1
	cntF[ta] += 1
	cntF[tb] += 1
	solve.Unite(ta,tb)

for _ in range(K):
	tc,td = map(int, input().split())
	tc -= 1
	td -= 1
	if solve.isSameGroup(tc,td):
		cntF[tc] += 1
		cntF[td] += 1

ans = []
for i in range(N):
	ans.append(solve.Count(i) - cntF[i] - 1)
print(*ans)

Submission status: Accepted

Solution code:
from collections import Counter


def same_group():
    class UnionFind(object):
        def __init__(self, n):
            self.par = [i for i in range(n)]
            self.rank = [0 for _ in range(n)]

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

        def unite(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    N, M, K = map(int, input().split())

    uf = UnionFind(N)
    friends = {i: 0 for i in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if uf.find(a) != uf.find(b):
            uf.unite(a, b)

        friends[a] += 1
        friends[b] += 1

    for i in range(N):
        uf.find(i)

    num_per_group = Counter(uf.par)

    blocks = {i: 0 for i in range(N)}
    for _ in range(K):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if uf.par[c] == uf.par[d]:
            blocks[c] += 1
            blocks[d] += 1

    print(*[max(num_per_group[uf.par[i]] - friends[i] - blocks[i] - 1, 0) for i in range(N)])


same_group()

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la > lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
n,m,k=map(int, input().split( ))
F = [tuple(map(int, input().split( ))) for _ in range(m)]
B = [tuple(map(int, input().split( ))) for _ in range(k)]
Fx = [[] for i in range(n+1)]
Bx = [[] for i in range(n+1)]
for a,b in F:
    Fx[a].append(b)
    Fx[b].append(a)
for a,b in B:
    Bx[a].append(b)
    Bx[b].append(a)
#友達関係での連結成分で分解
#連結成分中から2つ選ぶ場合の数から友達関係とブロック関係を引く
#各人ごと
#https://tjkendev.github.io/procon-library/python/union_find/union_find.html
*p, = range(n+1)
rank = [1]*(n+1)
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:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1
for a,b in F:
    unite(a,b)
dic = {}
for i in range(1,n+1):
    if root(i) in dic:
        dic[root(i)] +=1
    else:
        dic[root(i)] = 1
for i in range(1,n+1):
    ans = dic[root(i)]-1
    for b in Fx[i]:
        if root(b)==root(i):
            ans-=1
    for b in Bx[i]:
        if root(b)==root(i):
            ans-=1
    print(ans,end=" ")

Submission status: Accepted

Solution code:

import numpy as np


from functools import *
import sys
sys.setrecursionlimit(100000)


def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


mod = 10**9+7


class UnionFind:
    def __init__(self, size):
        # -nが木のroot
        # 親ノードの位置を格納
        self.table = [-1 for i in range(size)]

    def _find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def find(self, x):
        if self.table[x] < 0:
            return x
        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 get_ntree(self):
        res = 0
        for c in self.table:
            if c < 0:
                res += 1
        return res

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

    def get_nclass(self):
        done = []
        for x in range(len(self.table)):
            if x in done:
                continue
            while self.table[x] >= 0:
                done.append(x)
                x = self.table[x]

    def get_nodenum(self):
        res = []
        for t in self.table:
            if t < 0:
                res.append(-t)

        return res


def ij_to_n(i, j, W):
    return i*W+j


def n_to_ij(n, W):
    return (n//W, n % W)


if __name__ == '__main__':

    N, M, K = acinput()

    uf = UnionFind(N)
    A=[[]for i in range(N)]
    for i in range(M):
        tmp = acinput()
        uf.union(tmp[0]-1, tmp[1]-1)
        A[tmp[0]-1].append(tmp[1]-1)
        A[tmp[1]-1].append(tmp[0]-1)


    block=[[]for i in range(N)]
    for i in range(K):
        tmp = acinput()
        block[tmp[0]-1].append(tmp[1]-1)
        block[tmp[1]-1].append(tmp[0]-1)

    nt = uf.get_ntree()
    res=[]
    for i in range(N):
        nblock = 0
        for sb in block[i]:
            if uf.is_same(sb,i):
                nblock += 1

        nn =(-uf.table[uf.find(i)])

        nn-=1
        
        #print(uf.find(i),nn, A[i], nblock)
        tmp = nn-(len(A[i]))-nblock
        res.append(tmp)

    print(" ".join(map(str,res)))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())
uf1 = UnionFind(N)
frs = [0] * N
for _ in range(M):
    a, b = map(int, input().split())
    uf1.union(a-1, b-1)
    frs[a-1] += 1
    frs[b-1] += 1
ans = []
for i in range(N):
    ans.append(uf1.size(i) - frs[i] - 1)
for _ in range(K):
    c, d = map(int, input().split())
    if uf1.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
from collections import defaultdict
n,m,k=map(int,input().split())
tree = UnionFind(n)
friend=defaultdict(int)
block =defaultdict(int)

ab=[]
for _ in range(m):
    a,b=map(int,input().split())
    ab.append((a,b))
    
for a,b in ab:
    tree.union(a-1,b-1)
    
for a,b in ab:
    if tree.same(a-1,b-1):
        friend[a-1] +=1
        friend[b-1] +=1
    
for _ in range(k):
    c,d=map(int,input().split())
    if tree.same(c-1,d-1):
        block[c-1] +=1
        block[d-1] +=1
    
ans=[]
for i in range(n):
    l = tree.size(i) - block[i]  - friend[i]
    ans.append(l-1)
print(*ans)

Submission status: Accepted

Solution code:
n,m,k = (int(num) for num in input().split())
f_l = [0] * n
b_l = [[] for _ in range(n)]
par = [i for i in range(n)]
rank = [0] * n
size = [1] * n

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])
        
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    elif rank[x] < rank[y]:
        par[x] = y
        size[y] += size[x]
    else:
        par[y] = x
        size[x] += size[y]
        if rank[x] == rank[y]:
            rank[x] += 1
    return
            
def isSame(x,y):
    return find(x) == find(y)

for _ in range(m):
    a,b = (int(num) for num in input().split())
    a -= 1
    b -= 1
    f_l[a] += 1
    f_l[b] += 1
    unite(a,b)
    #print("par:  ", par)
    #print("rank: ", rank)
    
for _ in range(k):
    a,b = (int(num) for num in input().split())
    a -= 1
    b -= 1
    b_l[a].append(b)
    b_l[b].append(a)
    
ans = ""

for i in range(n):
    ans_num = size[find(i)] - f_l[i] -1
    for num in b_l[i]:
        if isSame(i,num):
            ans_num -= 1
    ans_num = max(ans_num,0)
    ans += str(ans_num) + " "
    
print(ans)

Submission status: Accepted

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

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

n,m,k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(k)]
ans = [0] * n
u = UnionFind(n)
for a,b in ab:
  a-=1
  b-=1
  u.union(a,b)
for i in range(n):
  ans[i] = u.get_size(i)-1
for a,b in ab:
  a-=1
  b-=1
  if u.is_same(a,b):
    ans[a] -= 1
    ans[b] -= 1
for c,d in cd:
  c-=1
  d-=1
  if u.is_same(c,d):
    ans[c] -= 1
    ans[d] -= 1	
print(*ans)

Submission status: Accepted

Solution code:
def rt(x):
    while x!=T[x][0]:
        x = T[x][0]
    return x
N,M,K = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
D = {i:[] for i in range(1,N+1)}
for _ in range(K):
    c,d = map(int,input().split())
    D[c].append(d)
    D[d].append(c)
T = {i:[i,0] for i in range(1,N+1)}
for a in G:
    for b in G[a]:
        r1 = rt(a)
        r2 = rt(b)
        if r1!=r2:
            if T[r1][1]>=T[r2][1]:
                T[r2][0] = r1
                if T[r1][1]==T[r2][1]:
                    T[r1][1] += 1
            else:
                T[r1][0] = r2
C = {}
for i in range(1,N+1):
    rt1 = rt(i)
    if rt1 not in C:
        C[rt1] = 0
    C[rt1] += 1
B = [0 for _ in range(N+1)]
for i in range(1,N+1):
    rt1 = rt(i)
    numc = C[rt1]
    numd = len(G[i])
    B[i] = numc-1-numd
    for j in D[i]:
        if rt(j)==rt1:
            B[i] -= 1
print(*B[1:])

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]
        

from collections import defaultdict, Counter
count_friend = Counter()
# friends = defaultdict(list)
friends_cluster = Counter()
# blocks = defaultdict(set)
count_block = Counter()
N, M, K = map(int, input().split())
ds = DisjointSet(N+1)
# graph = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    ds.unite(A, B)
    count_friend[A] += 1
    count_friend[B] += 1
for i in range(K):
    C, D = map(int, input().split())
    if ds.same(C, D):
        count_block[C] += 1
        count_block[D] += 1
c_ids = [ds.findSet(i) for i in range(N+1)]
for i in range(1, N+1):
    friends_cluster[c_ids[i]] += 1
ans = []
for i in range(1, N+1):
    c_id = c_ids[i]
    ans += [friends_cluster[c_id]-count_block[i]-count_friend[i]-1]
print(' '.join(list(map(str, ans))))
# print(ds.p)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m,k=map(int,input().split())
friend=[[]for _ in range(n+1)]
block=[[] for _ in range(n+1)]
#union-find
par=[-1]*(n+1)
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def size(x):
    return -par[find(x)]
def unite(x,y):
    if find(x)==find(y):
        return False
    if size(x)<size(y):
        x,y=y,x
    X=find(x)
    Y=find(y)
    par[X]+=par[Y]
    par[Y]=X
    return True
def is_same(x,y):
    return find(x)==find(y)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].append(b)
    friend[b].append(a)
    unite(a,b)
for _ in range(k):
    c,d=map(int,input().split())
    if is_same(c,d):
        block[c].append(d)
        block[d].append(c)
ans=[0]*(n+1)

for i in range(1,n+1):
    f=size(i)-1-len(friend[i])
    b=len(block[i])
    ans[i]=f-b
print(*ans[1:], sep=' ')

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
AB=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  AB[a-1].append(b)
  AB[b-1].append(a)

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
      
uf=UnionFind(N)
for i in range(N):
  for j in AB[i]:
    uf.union(i,j-1)

ans=[0]*N
for i in range(N):
  ans[i]=uf.size(i)-1-len(AB[i])
for i in range(K):
  c,d=map(int,input().split())
  if uf.same(c-1,d-1):
    ans[c-1]-=1
    ans[d-1]-=1
print(*ans)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
connect = [[] for _ in range(n)]
cCnt = [0 for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    connect[a - 1].append(b - 1)
    cCnt[a - 1] += 1
    connect[b - 1].append(a - 1)
    cCnt[b - 1] += 1

group = [0 for _ in range(n)]
gNum = 0
import queue
for i in range(n):
    if group[i]:
        continue
    gNum += 1
    next = queue.Queue()
    for j in connect[i]:
        group[j] = gNum
        next.put(j)
    group[i] = gNum

    while not next.empty():
        j = next.get()
        group[j] = gNum
        for l in connect[j]:
            if not group[l]:
                group[l] = gNum
                next.put(l)

hunaka = [0 for i in range(n)]
for i in range(k):
    c, d = map(int, input().split())
    if group[c - 1] != group[d - 1]:
        continue
    hunaka[c - 1] += 1
    hunaka[d - 1] += 1

groupCnt = [0 for _ in range(gNum + 1)]
for i in group:
    groupCnt[i] += 1

for i in range(n):
    tmp = groupCnt[group[i]]
    tmp -= cCnt[i]
    tmp -= hunaka[i]
    tmp -= 1
    print(tmp, end = " ")

Submission status: Accepted

Solution code:
from operator import itemgetter

N, M, K = map(int, input().split())

par = [i for i in range(N)]
rank = [1 for i in range(N)]

def get_root(A):
    if par[A] == A:
        return A
    par[A] = get_root(par[A])
    return par[A]

def connect(A, B):
    A = get_root(A)
    B = get_root(B)
    if A == B:
        return
    if rank[A] < rank[B]:
        A, B = B, A
    par[B] = A
    rank[A] += rank[B]
    rank[B] = 0


def verify_connect(A, B):
    if get_root(A) == get_root(B):
        return True
    else:
        return False


# like
like_path = [[] for i in range(N)]
like_query = [input() for i in range(M)]
dislike_query = [input() for i in range(K)]
for line in like_query:
    A, B = map(int, line.split())
    connect(A-1, B-1)
    like_path[A-1].append(B-1)
    like_path[B-1].append(A-1)

tmp_ans = []
for i in range(N):
    tmp_ans.append(rank[get_root(i)]-len(like_path[i])-1)

for line in dislike_query:
    A, B = map(int, line.split())
    if verify_connect(A-1, B-1):
        tmp_ans[A-1] -= 1
        tmp_ans[B-1] -= 1

print(" ".join(map(str, tmp_ans)))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
cd = [list(map(int,input().split())) for i in range(k)]
num = [0]*(n+1)
g = [[] for i in range(n+1)]
uf = UnionFind(n+1)
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  uf.union(a,b)
for c,d in cd:
  if uf.same(c,d) == True:
    g[c].append(d)
    g[d].append(c)
for i in range(1,n+1):
  print(uf.size(i)-len(g[i])-1,end=" ")

Submission status: Accepted

Solution code:
import sys, math
sys.setrecursionlimit(10**5 + 10)

def input():
    return sys.stdin.readline()[:-1]

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M, K = map(int,input().split())
    uf = UnionFind(N)
    F = [[] for k in range(N)]
    for k in range(M):
        a, b = map(int,input().split())
        uf.union(a-1,b-1)
        F[a-1].append(b-1)
        F[b-1].append(a-1)
    A = [uf.size(k)-len(F[k])-1 for k in range(N)]
    for k in range(K):
        c, d = map(int,input().split())
        if uf.same(c-1,d-1) == True:
            A[c-1] -= 1
            A[d-1] -= 1
    print(*A)

if __name__ == '__main__':
    main()