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:
import sys
sys.setrecursionlimit(1000000)
n,m,k=map(int,input().split())
stock=[[] for i in range(n)]
ter=[0]*n
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    ans[a-1]-=1
    ans[b-1]-=1
def dfs(j,k):
    size[k]+=1
    for next_j in stock[j]:
        if ter[next_j]==0:
            ter[next_j]=k
            dfs(next_j,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)

for i in range(n):
    ans[i]+=size[ter[i]]-1
for i in range(k):
    c, d = map(int, input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
n,m,k=map(int,input().split())
stock=[[] for i in range(n)]
ter=[0]*n
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    stock[a-1].append(b-1)
    stock[b-1].append(a-1)
    ans[a-1]-=1
    ans[b-1]-=1
def dfs(j,k):
    size[k]+=1
    for next_j in stock[j]:
        if ter[next_j]==0:
            ter[next_j]=k
            dfs(next_j,k)
total=0
size=[0]*(n+1)
for i in range(n):
    if ter[i]==0:
        total+=1
        ter[i]=total
        dfs(i,total)

for i in range(n):
    ans[i]+=size[ter[i]]-1
for i in range(k):
    c, d = map(int, input().split())
    if ter[c-1]==ter[d-1]:
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent=[i for i in range(n)]
        self.rank=[1]*n#木の高さ
        self.size=[1]*n#size[i]はiを根とするグループのサイズ

    def find(self,x):#ｘの根（親）を返す
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.find(self.parent[x])#経路圧縮
            return self.parent[x]

    def unite(self,x,y):#ｘ、ｙの集合の統合
        x=self.find(x)
        y=self.find(y)
        if x!=y:
            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 group_size(self,x):#ｘが属する集合の大きさ
        return self.size[self.find(x)]
    def is_same(self,x,y):#ｘ、ｙが同じ集合に属するかを判定する
        return self.find(x)==self.find(y)

n,m,k=map(int,input().split())

uf=UnionFind(n)
ans = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a-1,b-1)
    ans[a - 1] -= 1
    ans[b - 1] -= 1
for i in range(k):
    c, d = map(int, input().split())
    if uf.is_same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1

for i in range(n):
    ans[i]+=uf.group_size(i)-1
    print(ans[i])

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, n):
        self.par = list(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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x

        self.par[y] = x
        self.size[x] += self.size[y]

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

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


N, M, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
Y = [list(map(int, input().split())) for _ in range(K)]

friend = [[] for _ in range(N + 1)]
for a, b in X:
    friend[a].append(b)
    friend[b].append(a)

block = [[] for _ in range(N + 1)]
for c, d in Y:
    block[c].append(d)
    block[d].append(c)

t = UnionFind(N + 1)
for a, b in X:
    t.unite(a, b)

ans = []
for i in range(1, N + 1):
    cnt = t.get_size(i) - len(friend[i]) - 1
    for v in block[i]:
        cnt -= int(t.is_same(i, v))
    ans.append(cnt)

print(*ans)

Submission status: Accepted

Solution code:
import sys
import queue
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	# = int(input())
	n, m, k = tin()
	#s = input()
	friend_l = [[] for _ in range(n)]
	for _ in range(m):
		a, b = tin()
		a, b = a-1, b-1
		friend_l[a].append(b)
		friend_l[b].append(a)
	
	friend_group=[-1]*n
	gid=1
	st=0
	while st < n:
		if friend_group[st] > 0:
			st += 1
			continue
		friend_group[st] = gid
		qq=queue.Queue()
		qq.put(st)
		while not qq.empty():
			f = qq.get()
			for t in friend_l[f]:
				if friend_group[t] == -1:
					friend_group[t] = gid
					qq.put(t)
		gid += 1
				
	num_mem = collections.Counter(friend_group)
	
	#about block
	bl=[[] for _ in range(n)]
	bln = [0]*n
	for _ in range(k):
		a,b = tin()
		a,b = a-1, b-1
		if friend_group[a] == friend_group[b]:
			bln[a]+=1
			bln[b]+=1
			
	ret=[]
		
	for i in range(n):
		full = num_mem[friend_group[i]]
		fn = len(friend_l[i])
		p=(full-fn-bln[i] -1)
		ret.append(p)
	print(*ret)
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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())
uf = UnionFind(n)
data = [0]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    data[a] += 1
    data[b] += 1
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
        data[c] += 1
        data[d] += 1
print(*[uf.size(i)-data[i]-1 for i in range(n)])

Submission status: Accepted

Solution code:
from collections import Counter


class UnionFind:
    from collections import deque

    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = self.deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


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

n_friends = Counter()
n_groups = Counter()
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    uf.union(a, b)
    n_friends[a] -= 1
    n_friends[b] -= 1

for _ in range(K):
    c, d = map(int, input().split(' '))
    c -= 1
    d -= 1
    if uf.find(c, d):
        n_friends[c] -= 1
        n_friends[d] -= 1

for n in range(N):
    n_groups[uf._root(n)] += 1

print(*[n_friends[n] + n_groups[uf._root(n)] - 1 for n in range(N)])

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 = list(map(int, input().split()))
uf = UnionFind(n)
like = [[] for i in range(n)]
dislike = [[] for i in range(n)]
for i in range(m):
  a, b = list(map(int, input().split()))
  a -= 1
  b -= 1
  like[a].append(b)
  like[b].append(a)
  uf.union(a, b)
for i in range(k):
  a, b = list(map(int, input().split()))
  a -= 1
  b -= 1
  dislike[a].append(b)
  dislike[b].append(a)

for i in range(n):
  team = uf.find(i)
  ans = uf.size(team) - len(like[i])
  for j in dislike[i]:
    if uf.find(j) == team:
      ans -= 1
  print(ans - 1, " ", end ="")

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.par = [-1] * n


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True


    def root(self, x):
        path = []
        while self.par[x] >= 0:
            path.append(x)
            x = self.par[x]
        for y in path:
            self.par[y] = x
        return x


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


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


n, m, k = map(int, input().split())

friends = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].append(b)
    friends[b].append(a)

blocks = [[] for _ in range(n)]
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    blocks[c].append(d)
    blocks[d].append(c)

uni = UnionFind(n)
for i, v in enumerate(friends):
    for j in v:
        uni.unite(i, j)

for i in range(n):
    ans = uni.size(i) - len(friends[i]) - 1
    for block in blocks[i]:
        if uni.same(i, block):
            ans -= 1
    print(ans, end=' ')

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())
uf = UnionFind(n+1)
n_rlts = [0]*(n+1)
for i in range(m):
    a,b = map(int, input().split())
    n_rlts[a] += 1
    n_rlts[b] += 1
    uf.union(a,b)
for i in range(k):
    c,d = map(int, input().split())
    if uf.same(c,d):
        n_rlts[c] += 1
        n_rlts[d] += 1
res = ""
for i in range(1,n+1):
    res += str(uf.size(i)-1-n_rlts[i]) + " "
print(res[:-1])

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    n, m, k = list(map(int, input().split()))
    friendships = [tuple(map(int, input().split())) for _ in range(m)]
    blockships = [tuple(map(int, input().split())) for _ in range(k)]

    components = list(range(n))
    friends = { }

    for u, v in friendships:
        u -= 1
        v -= 1
        if u not in friends:
            friends[u] = []
        if v not in friends:
            friends[v] = []
        friends[u].append(v)
        friends[v].append(u)

    blocks = { }
    for u, v in blockships:
        u -= 1
        v -= 1
        if u not in blocks:
            blocks[u] = []
        if v not in blocks:
            blocks[v] = []
        blocks[u].append(v)
        blocks[v].append(u)

    # union-find
    cur_comp = 0
    visited = set()

    def bfs(node):
        st = [node]
        comp = node
        while st:
            n = st.pop()
            if n in visited:
                continue
            components[n] = comp
            visited.add(n)
            if n in friends:
                for nbor in friends[n]:
                    st.append(nbor)


    for u in range(n):
        bfs(u)

    hist = Counter(components)
    new_friends = [0] * n

    # for each user, look up component, calculate total
    # size of component, subtract number of users in the block
    # list that are also in that component
    for u in range(n):
        comp = components[u]
        comp_size = hist[comp]
        n_blocked = blocks[u] if u in blocks else set()
        n_friends = friends[u] if u in friends else set()
        n_same_comp = list(filter(lambda v: components[v] == comp, n_blocked))
        # print(u, n_friends, n_blocked, n_same_comp)
        new_friends[u] = comp_size - 1 - len(n_same_comp) - len(n_friends)

    print(' '.join(map(str, new_friends)))


main()

Submission status: Accepted

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


class Unionfind():  # 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)


# 解説AC
n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

uf = Unionfind(n)
frnd = [0] * n
for a, b in ab:
    uf.union(a - 1, b - 1)
    frnd[a - 1] += 1
    frnd[b - 1] += 1

brck = [0] * n
for c, d in cd:
    if uf.same(c - 1, d - 1):
        brck[c - 1] += 1
        brck[d - 1] += 1

ans = []
for i in range(n):
    ans.append(uf.size(i) - frnd[i] - brck[i] - 1)
print(*ans)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
 
par=[-1]*N
num=[0]*N
 
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
 
def union(x,y):
    p,q=find(x),find(y)
    if p==q:
        return
    if p>q:
        p,q=q,p
    par[p]+=par[q]
    par[q]=p   
 
def size(x):
    return -par[find(x)]
 
def same(x,y):
    return find(x)==find(y)
        
 
for _ in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    union(a,b)
    num[a]+=1
    num[b]+=1
 
for _ in range(K):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if same(c,d):
        num[c]+=1
        num[d]+=1
 
for i in range(N):
    print(size(i)-1-num[i],end=" ")

Submission status: Accepted

Solution code:
class UnionFind:
    """
    size の要素数の UnionFind を管理する
    data 中の負数の要素が根となる
    """

    def __init__(self, size):
        # 根は子を含む集合のデータ数を負数でもつ
        self.data = [-1] * size

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False

        # y の方がデータ数を多く
        if self.data[x] < self.data[y]:
            x, y = y, x

        # y に x をつなげる
        self.data[y] += self.data[x]
        self.data[x] = y
        return True

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

    def size(self, x):
        """
        根は負数でデータ数を管理しているのでそれを返す
        """
        return -self.data[self.root(x)]


N, M, K = [int(_) for _ in input().split()]
NG = [0] * (N + 1)
uf = UnionFind(N + 1)
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    uf.merge(a, b)
    NG[a] += 1
    NG[b] += 1

# KG = [[] for _ in range(N + 1)]
for i in range(K):
    a, b = [int(_) for _ in input().split()]
    if uf.root(a) == uf.root(b):
        NG[a] += 1
        NG[b] += 1

res = [0] * (N)
for i in range(1, N + 1):
    cnt = uf.size(i) - NG[i] - 1
    res[i-1]=cnt
print(*res)

Submission status: Accepted

Solution code:
class UnionFind:
    """
    size の要素数の UnionFind を管理する
    data 中の負数の要素が根となる
    """

    def __init__(self, size):
        # 根は子を含む集合のデータ数を負数でもつ
        self.data = [-1] * size

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False

        # y の方がデータ数を多く
        if self.data[x] < self.data[y]:
            x, y = y, x

        # y に x をつなげる
        self.data[y] += self.data[x]
        self.data[x] = y
        return True

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

    def size(self, x):
        """
        根は負数でデータ数を管理しているのでそれを返す
        """
        return -self.data[self.root(x)]


N, M, K = [int(_) for _ in input().split()]
MG = [0] * (N + 1)
uf = UnionFind(N + 1)
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    uf.merge(a, b)
    MG[a] += 1
    MG[b] += 1

KG = [[] for _ in range(N + 1)]
for i in range(K):
    a, b = [int(_) for _ in input().split()]
    KG[a].append(b)
    KG[b].append(a)

res = [0]*(N)
for i in range(1,N+1):
    cnt = uf.size(i) - MG[i]-1
    for k in KG[i]:
        if uf.root(i)==uf.root(k):
            cnt-=1
    res[i-1] =cnt
print(*res)

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]


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

#初期化
#根なら-size,子なら親の頂点
par = [-1]*N

G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    unite(a-1, b-1)

ans = [size(v) - len(G[v]) - 1 for v in range(N)]

H = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    if same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
    
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
# dfs
import collections,sys
sys.setrecursionlimit(10**9)
n,m,k = map(int, input().split())

friend = [[]*(n+1) for _ in range(n+1)]
block = [[]*(n+1) for _ in range(n+1)]
teams = [0]*(n+1)
for _ in range(m):
  a,b = map(int, input().split())
  friend[a].append(b)
  friend[b].append(a)
for _ in range(k):
  c,d = map(int, input().split())
  block[c].append(d)
  block[d].append(c)
  
def dfs(i):
  teams[i] = team
  for j in friend[i]:
    if teams[j] != 0:
      continue
    dfs(j)

team=1
for i in range(1,n+1):
  if teams[i] != 0:
    continue
  dfs(i)
  team+=1

c = collections.Counter(teams)

for i in range(1,n+1):
  temp = c[teams[i]]-len(friend[i])-1
  for j in block[i]:
    if teams[j] == teams[i]:
      temp -= 1
  print(temp, end='')
  if i != n:
    print(" ", end='')

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
#Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
par = [-1 for i in range(n)]
l = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
    l[a-1] += 1
    l[b-1] += 1
for i in range(k):
    c, d = map(int, input().split())
    if same(c-1, d-1):
        l[c-1] += 1
        l[d-1] += 1
for i in range(n):
    print(size(i) - l[i] - 1, end=" ")

Submission status: Accepted

Solution code:
# D - Friend Suggestions

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x) == self.root(y)

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

N,M,K = map(int,input().split())
friend = UnionFind(N+1)
block = [1]*(N+1)
for _ in range(M):
    x,y = map(int,input().split())
    block[x] += 1
    block[y] += 1
    friend.union(x,y)
for _ in range(K):
    x,y = map(int,input().split())
    if friend.same(x,y):
        block[x] += 1
        block[y] += 1
ans = [friend.size(i)-block[i] for i in range(1,N+1)]
print(*ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


def main():
    N, M, K = map(int, readline().split())
    AB = [tuple(int(s) - 1 for s in readline().split()) for _ in range(M)]
    CD = [tuple(int(s) - 1 for s in readline().split()) for _ in range(K)]

    G = [[] for _ in range(N)]
    for a, b in AB:
        G[a].append(b)
        G[b].append(a)

    H = [[] for _ in range(N)]
    for c, d in CD:
        H[c].append(d)
        H[d].append(c)

    uf = UnionFind(N)
    for a, b in AB:
        uf.union(a, b)

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i) - len(G[i]) - 1
        for j in H[i]:
            if uf.same(i, j):
                ans[i] -= 1

    print(' '.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n,m,k = map(int, input().split())
f = [[] for _ in range(n)]
g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    f[a].append(b)
    f[b].append(a)

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

d = {}
parent = [-1] * n
seen = [False] * n

for i in range(n):
    if seen[i]:
        continue
    stack = deque()
    d[i] = set([i])
    stack = [i]
    while stack:
        v = stack.pop()
        seen[v] = True
        parent[v] = i
        for nv in f[v]:
            if seen[nv]:
                continue
            d[i].add(nv)
            stack.append(nv)

ans = [0] * n
for i in range(n):
    group = d[parent[i]]
    tmp = len(group) - len(f[i]) - 1
    for j in g[i]:
        if j in group:
            tmp -= 1
    ans[i] = tmp

print(*ans)

Submission status: Accepted

Solution code:
# AtCoder

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 _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uf = UnionFind(N)
friend = [0]*N
blocked = [0]*N

for a, b in AB:
    uf.union(a-1, b-1)
    friend[a-1] += 1
    friend[b-1] += 1

for c, d in CD:
    if uf.same(d-1, c-1):
        blocked[c-1] += 1
        blocked[d-1] += 1

ans = [uf.size(i)-friend[i]-blocked[i]-1 for i in range(N)]
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
import collections
class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0]*N
        self.count = 0
    def root(self, a):
        if self.parent[a]==a:
            return a
        else:
            self.parent[a]=self.root(self.parent[a])
            return self.parent[a]
    def size(x):
        return -par[root(x)]

    def is_same(self, a, b):
        return self.root(a)==self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return

        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
def main():
    n,m,k=map(int, input().split())
    friend = [0]*n
    fr = UnionFind(n)
    blocklist = [0]*n
    for i in range(m):
        a,b = map(int, input().split())
        fr.unite(a-1,b-1)
        friend[a-1]+=1
        friend[b-1]+=1
    for i in range(k):
        c,d=map(int, input().split())
        if(fr.root(c-1)==fr.root(d-1)):
            blocklist[c-1]+=1
            blocklist[d-1]+=1
    
    res = []
    dd = collections.defaultdict(int)
    for i in range(n):
        dd[fr.root(i)]+=1
    for i in range(n):
        res.append(dd[fr.root(i)]- blocklist[i] - friend[i]-1)
    print(*res)

if __name__ == '__main__':
    main()