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:
from collections import defaultdict


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())


if __name__ == '__main__':
    n, m, k = list(map(int, input().split()))
    friends = UnionFind(n)
    ng_dict = defaultdict(list)

    for i in range(m):
        data = list(map(int, input().split()))
        x = data[0] - 1
        y = data[1] - 1

        friends.union(x, y)
        ng_dict[x].append(y)
        ng_dict[y].append(x)

    for i in range(k):
        data = list(map(int, input().split()))
        x = data[0] - 1
        y = data[1] - 1

        if friends.same(x, y):
            ng_dict[x].append(y)
            ng_dict[y].append(x)

    for i in range(n):
        print(friends.size(i) - len(ng_dict[i]) - 1, end=" ")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

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

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

ab = []
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

cd = [list(map(lambda x: int(x)-1, input().split())) for _ in range(k)]
ans = [uf.count_member(i)-1 for i in range(n)]

for a, b in ab:
    if uf.find(a) == uf.find(b):
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:
# Union Find
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) ]

# print(ab)
# print(cd)

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())

uf = UnionFind(n)

ls_friend = [0]*n
for i in range(m):
    ls_friend[ ab[i][0]-1 ] += 1
    ls_friend[ ab[i][1]-1 ] += 1
    uf.union( ab[i][0]-1, ab[i][1]-1 )

ls_block = [0]*n
for i in range(k):
    if uf.same( cd[i][0]-1, cd[i][1]-1 ):
        ls_block[ cd[i][0]-1 ] += 1
        ls_block[ cd[i][1]-1 ] += 1
    else:
        pass

# print(uf)

ls_ans = [0]*n
for i in range(n):
    ls_ans[i] += uf.size(i) - 1 - ls_friend[i] - ls_block[i]

print(" ".join(list(map(str,ls_ans))))

Submission status: Accepted

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

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

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

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

groups = [-1]*(n+1)
n_groups = []
g = 0
for i in range(1, n+1):
    if groups[i]>=0:
        continue
    stack = [i]
    cnt = 0
    groups[i] = g
    while len(stack)>0:
        node = stack.pop()
        for c_node in friends[node]:
            if groups[c_node]>=0:
                continue
            stack.append(c_node)
            groups[c_node] = g
            cnt += 1
    n_groups.append(cnt)
    g += 1

ans = []
for i in range(1, n+1):
    tmp = n_groups[groups[i]]
    for j in friends[i]:
        if groups[i] == groups[j]:
            tmp -= 1
    for j in blocks[i]:
        if groups[i] == groups[j]:
            tmp -= 1
    ans.append(tmp)

print(*ans)

Submission status: Accepted

Solution code:
"""

AtCoder Beginner Contest 157  D - Friend Suggestions


友達関係でUnionを作る。そのUnion内で、友達関係でも、Union内のブロック関係でもないものが友達候補
なので、
・友達関係でUnionFindでUnion化し、
・それぞれのUnionに所属する人数を調べて、自分を除く所属人数を友達候補の候補（変な表現だが）として、
・自分と友達関係の個数＆おなじUnionかつブロック関係の個数を引く
でOK

"""

class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N # 最初はそれぞれのノードが誰ともUnionをつくってないから木の深さが０
        self.count = 0 # unite回数
    
    # 根を返す
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            # 親を見に行く
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    
    # 同じUnionに属するかどうか
    def is_same(self, a, b):
        return self.root(a) == self.root(b)
    
    # 同じUnionにする
    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

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

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

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

uf = UnionFind(N)

for a,b in friends:
    if not uf.is_same(a,b):
        uf.unite(a,b)

ans = [0] * N


# i番目のUnionの人数
members = [0] * N
for i in range(N):
    members[uf.root(i)] += 1

for i in range(N):
    # iの人が所属するUnionの人数（i本人を除く）をもっておいて、ここから友達関係と、おなじUnionのブロック関係を除く
    ans[i] = members[uf.root(i)] - 1

# 友達関係にある人は同じUnionかつ、友達候補になりえないから除く
for a,b in friends:
    ans[a] -= 1
    ans[b] -= 1

# ブロック関係にあるc,dが、もし同じUnionであれば友達候補になりえないので除く
for c,d in blocks:
    if uf.is_same(c,d):
        ans[c] -= 1
        ans[d] -= 1


print(*ans)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N # 最初はそれぞれのノードが誰ともUnionをつくってないから木の深さが０
        self.count = 0 # unite回数
    
    # 根を返す
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            # 親を見に行く
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    
    # 同じUnionに属するかどうか
    def is_same(self, a, b):
        return self.root(a) == self.root(b)
    
    # 同じUnionにする
    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

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

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

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

uf = UnionFind(N)

for a,b in friends:
    if not uf.is_same(a,b):
        uf.unite(a,b)

ans = [0] * N


# i番目のUnionの人数
members = [0] * N
for i in range(N):
    members[uf.root(i)] += 1

for i in range(N):
    # iの人が所属するUnionの人数（i本人を除く）
    ans[i] = members[uf.root(i)] - 1

# 友達関係にある人は同じUnionかつ、友達候補になりえないから除く
for a,b in friends:
    ans[a] -= 1
    ans[b] -= 1

# ブロック関係にあるc,dが、もし同じUnionであれば友達候補になりえないので除く
for c,d in blocks:
    if uf.is_same(c,d):
        ans[c] -= 1
        ans[d] -= 1


print(*ans)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N # 最初はそれぞれのノードが誰ともUnionをつくってないから木の深さが０
        self.count = 0 # unite回数
    
    # 根を返す
    def root(self, a):
        if self.parent[a] == a:
            return a
        else:
            # 親を見に行く
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    
    # 同じUnionに属するかどうか
    def is_same(self, a, b):
        return self.root(a) == self.root(b)
    
    # 同じUnionにする
    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

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

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

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

uf = UnionFind(N)

for a,b in friends:
    if not uf.is_same(a,b):
        uf.unite(a,b)

ans = [0] * N

for i in range(N):
    _ = uf.root(i)

# i番目のUnionの人数
members = [0] * N
for i in range(N):
    members[uf.root(i)] += 1

for i in range(N):
    # iの人が所属するUnionの人数（i本人を除く）
    ans[i] = members[uf.root(i)] - 1

# 友達関係にある人は同じUnionかつ、友達候補になりえないから除く
for a,b in friends:
    ans[a] -= 1
    ans[b] -= 1

# ブロック関係にあるc,dが、もし同じUnionであれば友達候補になりえないので除く
for c,d in blocks:
    if uf.is_same(c,d):
        ans[c] -= 1
        ans[d] -= 1


print(*ans)

Submission status: Accepted

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

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

p=list(range(N))
r=[0]*N

def find(x):
  if p[x]==x:
    return x
  else:
    p[x]=find(p[x])
    return p[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if r[x]<r[y]:
    p[x]=y
  else:
    p[y]=x
    if r[x]==r[y]:
      r[x]+=1

nc=[1]*N
f=[0]*N

for i in range(M):
  a,b=map(int,input().split())
  nc[a-1]+=1
  nc[b-1]+=1
  unite(a-1,b-1)

for i in range(K):
  c,d=map(int,input().split())
  if find(c-1)==find(d-1):
    nc[c-1]+=1
    nc[d-1]+=1

for i in range(N):
  f[find(i)]+=1

print(*[f[find(i)]-nc[i] for i in range(N)])

Submission status: Accepted

Solution code:

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

p=[i for i in range(N)]
r=[0]*N

def find(x):
  if p[x]==x:
    return x
  else:
    p[x]=find(p[x])
    return p[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if r[x]<r[y]:
    p[x]=y
  else:
    p[y]=x
    if r[x]==r[y]:
      r[x]+=1

nc=[1]*N
f=[0]*N

for i in range(M):
  a,b=map(int,input().split())
  nc[a-1]+=1
  nc[b-1]+=1
  unite(a-1,b-1)

for i in range(K):
  c,d=map(int,input().split())
  if find(c-1)==find(d-1):
    nc[c-1]+=1
    nc[d-1]+=1

for i in range(N):
  f[find(i)]+=1

print(*[f[find(i)]-nc[i] for i in range(N)])

Submission status: Accepted

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


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

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

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

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    friend = UF_tree(N)
    d = defaultdict(int)

    for _ in range(M):
        A, B = map(int, input().split())
        friend.unite(A, B)
        d[A] += 1
        d[B] += 1

    for _ in range(K):
        C, D = map(int, input().split())
        if friend.isSame(C, D):
            d[C] += 1
            d[D] += 1

    ans = [friend.getNodeLen(i) - d[i] - 1 for i in range(1, N + 1)]
    print(*ans)

Submission status: Accepted

Solution code:
class UF():
    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]
n,m,k = map(int,input().split())
uf=UF(n)
 
F=[set() for _ in range(n)]
for i in range(m):
   a,b=map(int,input().split())
   uf.union(a-1,b-1)
   F[a-1].add(b-1)
   F[b-1].add(a-1)
 
B=[0]*n
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1
A=[]
for i in range(n):
    A.append(uf.size(i)-len(F[i])+B[i]-1)
print(*A)

Submission status: Accepted

Solution code:
class UF():
    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]
n,m,k = map(int,input().split())
uf=UF(n)
 
F=[set() for _ in range(n)]
for i in range(m):
   a,b=map(int,input().split())
   uf.union(a-1,b-1)
   F[a-1].add(b-1)
   F[b-1].add(a-1)
 
B=[0 for _ in range(n)]
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1
A=[]
for i in range(n):
    A.append(uf.size(i)-len(F[i])+B[i]-1)
print(*A)

Submission status: Accepted

Solution code:
def init(n) :  #n要素で初期化
	for i in range(n) :
		par[i] = i;
		rank[i] = 0;
		siz[i] = 1;

def root(x) :  #木の根を求める
	if par[x] == x :  #根
		return x;
	else :
		par[x] = root(par[x]);  #経路圧縮
		return par[x];

def same(x,y) :  #xとyが同じ集合に属するか否か
	return root(x) == root(y);

def unite(x,y) :  #xとyの属する集合を併合
	x = root(x);
	y = root(y);
	if x == y :
		return;
	if siz[x] < siz[y] :
		x,y = y,x;
	siz[x] += siz[y];
	par[y] = x;

def size(x) :
	return siz[root(x)];


nmk = input().split(' ');
n = int(nmk[0]);
m = int(nmk[1]);
k = int(nmk[2]);

par = [0]*n
rank = [0]*n
siz = [0]*n
init(n);

fre = [[0]*2 for i in range(m)];
bro = [[0]*2 for i in range(k)];
fb = [0]*n;

for i in range(m) :
	ab = input().split(' ');
	unite(int(ab[0])-1,int(ab[1])-1);
	fb[int(ab[0])-1] += 1;
	fb[int(ab[1])-1] += 1;
	fre[i][0] = int(ab[0]);
	fre[i][1] = int(ab[1]);

for i in range(k) :
	ab = input().split(' ');
	bro[i][0] = int(ab[0]);
	bro[i][1] = int(ab[1]);

for i in range(k) :
	if root(bro[i][0]-1) == root(bro[i][1]-1) :
		fb[bro[i][0]-1] += 1;
		fb[bro[i][1]-1] += 1;

print(size(0)-fb[0]-1,end='');
for i in range(1,n) :
    print('',size(i)-fb[i]-1,end='');
print();

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]

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

F=[set() for _ in range(n)]
for i in range(m):
   a,b=map(int,input().split())
   uf.union(a-1,b-1)
   F[a-1].add(b-1)
   F[b-1].add(a-1)

B=[0 for _ in range(n)]
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1
A=[]
for i in range(n):
    A.append(uf.size(i)-len(F[i])+B[i]-1)
print(*A)

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]

N, M, K = map(int,input().split())
uf = UnionFind(N)
F = [set() 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].add(B-1)
    F[B-1].add(A-1)

T = [0 for k in range(N)]
for k in range(K):
    C, D = map(int,input().split())
    if uf.same(C-1,D-1) == True:
        T[C-1] -= 1
        T[D-1] -= 1
A = []
for k in range(N):
    A.append(uf.size(k)-len(F[k])+T[k]-1)
print(*A)

Submission status: Accepted

Solution code:
def main():
    N, M, K = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [1 for i in range(N)]

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        # 連結成分のサイズを返す
        return rank[find_root(x)]

    fri = [[] for _ in range(N)]
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        fri[a-1].append(b-1)
        fri[b-1].append(a-1)
        unite(a-1, b-1)
    block = [[] for _ in range(N)]
    for i in range(K):
        a, b = (int(i) for i in input().split())
        if is_same_group(a-1, b-1):
            block[a-1].append(b-1)
            block[b-1].append(a-1)
    ans = []
    for i in range(N):
        cur = size(i) - len(fri[i]) - len(block[i]) - 1
        ans.append(cur)
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)

  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1

def Same(x, y, par):
  return Find(x, par) == Find(y, par)

def Size(x, par):
  return -par[Find(x, par)]

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

F = [0]*n
B = [0]*n

par = [-1]* n
rank = [0]*n

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    F[a] += 1
    F[b] += 1
    Unite(a, b, par, rank)

for i in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if Same(c, d, par):
        B[c] += 1
        B[d] += 1

ans = [0]*n
for i in range(n):
    ans[i] = Size(i, par)-F[i]-B[i]-1
print(*ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(M)]
    CD = [tuple(map(int, input().split())) for _ in range(K)]

    uf = UnionFindTree(N)
    friend_or_block = [set() for _ in range(N)]
    for a, b in AB:
        a, b = a-1, b-1
        uf.union(a, b)
        friend_or_block[a].add(b)
        friend_or_block[b].add(a)
    for c, d in CD:
        c, d = c-1, d-1
        if uf.same(c, d):
            friend_or_block[c].add(d)
            friend_or_block[d].add(c)
    
    print(*[uf.size(i) - len(friend_or_block[i]) - 1 for i in range(N)])

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
 
    # 要素xが属するグループの根を返す
    # 経路圧縮
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    # 要素xが属するグループと要素yが属するグループとを併合する
    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
 
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
 
    # 要素x,yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    # 要素xが属するグループに属する要素をリストで返す
    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 main():
    N,M,K = map(int,input().split())

    best_friend = [0] * N
    friend = UnionFind(N)
    for _ in range(M):
        A,B = map(int,input().split())
        best_friend[A-1] += 1
        best_friend[B-1] += 1
        friend.union(A-1, B-1)

    blocked = [[] for _ in range(N)]
    for _ in range(K):
        C,D = map(int,input().split())
        blocked[C-1].append(D-1)
        blocked[D-1].append(C-1)

    ans = [0] * N
    for i in range(N):
        # 友達候補 - 友達 - 自分
        ans[i] = friend.size(i) - best_friend[i] - 1
        # 嫌いな人は友達になれない
        for bad in blocked[i]:
            if friend.same(i, bad):
                ans[i] -= 1

    print(*ans, sep=" ")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

class UFT(): #Union-find tree class
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1



def solve():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    parent = UFT(N)
    connect = dict()
    NG = [0] * N
    friend = [0] * N
    for _ in range(M):
        x, y = map(int, input().split())
        parent.unite(x-1, y-1)
        friend[x-1] += 1
        friend[y-1] += 1
    for i in range(N):
        key = parent.find(i)
        if key in connect: connect[key] += 1
        else: connect[key] = 1
    for _ in range(K):
        c, d = map(int, input().split())
        if parent.find(c-1) == parent.find(d-1):
            NG[c-1] += 1
            NG[d-1] += 1
    Ans = [0] * N
    for i in range(N):
        Ans[i] = connect[parent.find(i)] - friend[i] - NG[i] - 1
    print(" ".join(map(str, Ans)))

    return 0

if __name__ =="__main__":
    solve()

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
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)]
u=UnionFind(n)
for a,b in ab:u.unite(a-1,b-1)
ans=[u.count(i)-1 for i in range(n)]
for a,b in ab:
  ans[a-1]-=1
  ans[b-1]-=1
for c,d in cd:
  if u.root_same(c-1,d-1):
    ans[c-1]-=1
    ans[d-1]-=1
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N,M,K = map(int,input().split())
f = [[] for _ in range(N+1)]
b = [[] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)

d = [None]*(N+1)
sys.setrecursionlimit(10**9)
def dfs(f,s,id):
    if(d[s] is None):
        d[s] = id
    for i in f[s]:
        if(d[i] is not None):
            continue
        dfs(f,i,id)
         
cnt = -1
for j in range(1,N+1):
    if(d[j] == None):
        cnt += 1
        dfs(f,j,cnt)
    
for i in range(K):
    x,y = map(int,input().split())
    if(d[x] == d[y]):
        b[x].append(y)
        b[y].append(x)

c = Counter(d)
for i in range(1,N+1):
    print(c[d[i]] - len(f[i]) - len(b[i])-1)