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:
#https://qiita.com/Kerzival/items/6923c2eb3b91be86f19f
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
N,M,K = list(map(int,input().split()))
uf = UnionFind(N)
fr = [0]*(N+1)
for i in range(M):
    [x_tmp,y_tmp] = list(map(int,input().split()))
    uf.Unite(x_tmp,y_tmp)
    fr[x_tmp] += 1
    fr[y_tmp] += 1
ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = uf.Count(i) - fr[i] - 1
for j in range(K):
    [x_tmp,y_tmp] = list(map(int,input().split()))
    if uf.isSameGroup(x_tmp,y_tmp):
        ans[x_tmp] -= 1
        ans[y_tmp] -= 1
print(' '.join(list(map(str,ans[1::]))))

Submission status: Accepted

Solution code:
n, m, k = [int(i) for i in input().split()]
ro = [-1] * n
r = [0] * n
co = [1] * n
ab = []
for _ in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    ab.append([a, b])
    while ro[a] != -1:
        a = ro[a]
    while ro[b] != -1:
        b = ro[b]
    if a != b:
        if r[a] > r[b]:
            ro[b] = a
            r[a] = max(r[a], r[b] + 1)
            co[a] += co[b]
        else:
            ro[a] = b
            r[b] = max(r[b], r[a] + 1)
            co[b] += co[a]
ans = []
for i in range(n):
    while ro[i] != -1:
        i = ro[i]
    ans.append(co[i]-1)
for a, b in ab:
    ans[a] -= 1
    ans[b] -= 1

for _ in range(k):
    c, d = [int(i) - 1 for i in input().split()]
    e, f = c, d
    while ro[c] != -1:
        c = ro[c]
    while ro[d] != -1:
        d = ro[d]
    if c == d:
        ans[e] -= 1
        ans[f] -= 1


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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        # Union find with component size
        # Negative means is a root where value is component size
        # Otherwise is index to parent
        self.p = [-1 for i in range(N)]

    def find(self, i):
        # Find root with path compression
        if self.p[i] >= 0:
            self.p[i] = self.find(self.p[i])
            return self.p[i]
        else:
            return i

    def union(self, i, j):
        # Union by size
        root1 = self.find(j)
        root2 = self.find(i)
        if root1 == root2:
            return
        size1 = -self.p[root1]
        size2 = -self.p[root2]
        if size1 < size2:
            self.p[root1] = root2
            self.p[root2] = -(size1 + size2)
        else:
            self.p[root2] = root1
            self.p[root1] = -(size1 + size2)

    def getComponentSize(self, i):
        return -self.p[self.find(i)]


from collections import defaultdict

N, M, K = list(map(int, input().split()))
friend = defaultdict(set)
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
block = defaultdict(set)
for i in range(K):
    c, d = list(map(int, input().split()))
    c -= 1
    d -= 1
    block[c].add(d)
    block[d].add(c)

uf = UnionFind(N)
for a, friends in friend.items():
    for b in friends:
        uf.union(a, b)

out = []
for a in range(N):
    count = uf.getComponentSize(a) - 1 - len(friend[a])
    for b in block[a]:
        if uf.find(a) == uf.find(b):
            count -= 1
    out.append(str(count))
print(" ".join(out))

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
blist=[[] for i in range(n+1)]
for i in range(k):
    a,b=map(int,input().split())
    blist[a].append(b)
    blist[b].append(a)
ans=[-1]*(n+1)
for i in range(1,n+1):
    if ans[i]==-1:
        s=set([i])
        q=[i]
        while q:
            for j in edge[q.pop()]:
                if j not in s:
                    s.add(j)
                    q.append(j)
        for j in s:
            tmp=len(s)-len(edge[j])-1
            for k in blist[j]:
                if k in s:
                    tmp-=1
            ans[j]=tmp
print(" ".join(map(str,ans[1:])))

Submission status: Accepted

Solution code:
'''
　 ∧_,,∧    究極奥義「WAがACになーれ！！」
　（`・ω・)つ━☆・*。
　⊂　　 ノ 　　　・゜+.
　 し’´Ｊ　　*・ 
'''
import sys
input = sys.stdin.readline
class UnionFind():
   # 作りたい要素数nで初期化
   # 使用するインスタンス変数の初期化
   def __init__(self, n):
       self.n = n
       # root[x]<0ならそのノードが根かつその値が木の要素数
       # rootノードでその木の要素数を記録する
       self.root = [-1]*(n+1)
       # 木をくっつける時にアンバランスにならないように調整する
       self.rnk = [0]*(n+1)
   # ノードxのrootノードを見つける
   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):
       # 入力ノードのrootノードを見つける
       x = self.Find_Root(x)
       y = self.Find_Root(y)
       # すでに同じ木に属していた場合
       if(x == y):
           return
       # 違う木に属していた場合rnkを見てくっつける方を決める
       elif(self.rnk[x] > self.rnk[y]):
           self.root[x] += self.root[y]
           self.root[y] = x
       else:
           self.root[y] += self.root[x]
           self.root[x] = y
           # rnkが同じ（深さに差がない場合）は1増やす
           if(self.rnk[x] == self.rnk[y]):
               self.rnk[y] += 1
   # xとyが同じグループに属するか判断
   def isSameGroup(self, x, y):
       return self.Find_Root(x) == self.Find_Root(y)
   # ノードxが属する木のサイズを返す
   def Count(self, x):
       return -self.root[self.Find_Root(x)]

n,m,k=map(int,input().split())
f=[set() for i in range(n)]
h=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    f[a].add(b)
    f[b].add(a)
    h.Unite(a,b)
ans=[h.Count(i)-len(f[i])-1 for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    if h.isSameGroup(a,b):
        ans[a]-=1
        ans[b]-=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())

import sys
input = sys.stdin.readline

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

friendgraph = [[] for _ in range(N)]
blockgraph = [[] for _ in range(N)]

uf = UnionFind(N)

for i in range(M):
    a = friend[i][0]-1
    b = friend[i][1]-1
    uf.union(a,b)
    friendgraph[a].append(b)
    friendgraph[b].append(a)

for i in range(K):
    a = blocked[i][0]-1
    b = blocked[i][1]-1
    blockgraph[a].append(b)
    blockgraph[b].append(a)

ans = []

for i in range(N):
    res = uf.size(i)-1
    res -= len(friendgraph[i])
    for b in blockgraph[i]:
        if uf.same(i,b):
            res -= 1

    ans.append(res)

print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
import collections

class UnionFind:

    def __init__(self, N):
        self.raw = [i for i in range(N)]

    def root(self, i):
        if self.raw[i] == i:
            return i
        self.raw[i] = self.root(self.raw[i])
        return self.raw[i]

    def unite(self, a, b):
        a_root = self.root(a)
        b_root = self.root(b)
        self.raw[a_root] = b_root

    def is_same(self, a, b):
        return self.root(a) == self.root(b)


def solve(N, M, K, AB, CD):
    uf = UnionFind(N)
    minus_count = [0 for _ in range(N)]
    for a, b in AB:
        uf.unite(a - 1, b - 1)
        minus_count[a - 1] += 1
        minus_count[b - 1] += 1
    for c, d in CD:
        if uf.is_same(c - 1, d - 1):
            minus_count[c - 1] += 1
            minus_count[d - 1] += 1
    counter = collections.Counter()
    roots = [uf.root(i) for i in range(N)]
    counter.update(roots)

    ans = []
    for i in range(N):
        ans.append(str(counter[uf.root(i)] - minus_count[i] - 1))
    return " ".join(ans)

if __name__ == "__main__":
    N, M, K = tuple(map(int, input().split(" ")))
    AB = []
    for _ in range(M):
        AB.append(tuple(map(int, input().split(" "))))
    CD = []
    for _ in range(K):
        CD.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, K, AB, CD))

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

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

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M, K = map(int, input().split())
    uft = UnionFindTree(N)
    friends = [0] * N
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        uft.unite(a, b)
        friends[a] += 1
        friends[b] += 1
    ans = [0] * N
    for g in uft.groups():
        for u in g:
            ans[u] = len(g) - 1 - friends[u]
    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if uft.is_same(c, d):
            ans[c] -= 1
            ans[d] -= 1
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
for _ in range(M) :
  a, b = map(int, input().split())
  friend[a - 1].append(b - 1)
  friend[b - 1].append(a - 1)
block = [[] for _ in range(N)]
for _ in range(K) :
  c, d = map(int, input().split())
  block[c - 1].append(d - 1)
  block[d - 1].append(c - 1)
  
visited = [-1] * N
color = 0
for i in range(N) :
  if visited[i] == -1 :
    q = [i]
    visited[i] = color
    while q :
      cur = q.pop()
      for nex in friend[cur] :
        if visited[nex] >= 0 : continue
        visited[nex] = color
        q.append(nex)    
    color += 1
    
cnt = Counter(visited)

ret = []
for i in range(N) :
  s = cnt[visited[i]]
  for j in block[i] :
    if visited[i] == visited[j] :
      s -= 1
  ret.append(s - len(friend[i]) - 1)
  
print(*ret)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
ab=[]
for i in range(m):
    a,b=map(int,input().split())
    ab.append((a-1,b-1))
cd=[]
for i in range(k):
    c,d=map(int,input().split())
    cd.append((c-1,d-1))

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

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n
for a,b in ab:
    unite(a,b)
dp1=[0]*n
for i in range(n):
    dp1[i]=size(i)-1
for a,b in ab:
    dp1[a]-=1
    dp1[b]-=1
for c,d in cd:
    if same(c,d):
        dp1[c]-=1
        dp1[d]-=1
print(' '.join(map(str,dp1)))

Submission status: Accepted

Solution code:
N, M, K = [int(_) for _ in input().split()]
AB = [[int(_) - 1 for _ in input().split()] for _ in range(M)]
CD = [[int(_) - 1 for _ in input().split()] for _ in range(K)]
friends = [0 for _ in range(N)]


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

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

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

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

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


uf = UnionFind(N)
for a, b in AB:
    uf.unite(a, b)
    friends[a] += 1
    friends[b] += 1
ans = [uf.size(i) - friends[i] - 1 for i in range(N)]
for c, d in CD:
    if uf.is_same(c, d):
        ans[c] -= 1
        ans[d] -= 1
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.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)
    block = UF_tree(N)
    cnt = defaultdict(int)
    for _ in range(M):
        a, b = map(int, input().split())
        cnt[a] += 1
        cnt[b] += 1
        friend.unite(a, b)

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

    ans = [0] * (N + 1)
    for i in range(1, N + 1):
        cand = friend.getNodeLen(i) - 1
        cand -= cnt[i]
        ans[i] = cand

    print(*ans[1:])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
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)]
u=UnionFind(N)
f=[[] for i in range(N)]
k=[[] for i in range(N)]
for a,b in AB:
    u.unite(a-1,b-1)
    f[a-1].append(b-1)
    f[b-1].append(a-1)
for c,d in CD:
    k[c-1].append(d-1)
    k[d-1].append(c-1)
print(*[u.size(i)-len(f[i])-sum([1 for j in k[i] if u.root(i)==u.root(j)])-1 for i in range(N)])

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = N//2 + N%2
    print(ans)
    return

def examB():
    A = [LI()for _ in range(3)]
    N = I()
    B = [I()for _ in range(N)]
    grid = [[False]*3 for _ in range(3)]
    ans = "No"
    for b in B:
        for i in range(3):
            for j in range(3):
                if A[i][j]==b:
                    grid[i][j] = True
    for i in range(3):
        flag = True
        for j in range(3):
            if not grid[i][j]:
                flag = False
        if flag:
            ans = "Yes"
    for i in range(3):
        flag = True
        for j in range(3):
            if not grid[j][i]:
                flag = False
        if flag:
            ans = "Yes"
    flag = True
    for i in range(3):
        if not grid[i][i]:
            flag = False
    if flag:
        ans = "Yes"
    flag = True
    for i in range(3):
        if not grid[i][2-i]:
            flag = False
    if flag:
        ans = "Yes"
    print(ans)
    return

def examC():
    N, M = LI()
    S = [LI()for _ in range(M)]
    ans = [-1]*N
    for s,c in S:
        s -= 1
        if ans[s]!=-1:
            if ans[s]!=c:
                print(-1)
                return
        ans[s] = c
    A = ""
    if ans[0]==0 and N>=2:
        print(-1)
        return
    elif ans[0]==-1 and N>=2:
        ans[0] = 1
    for i in ans:
        if i==-1:
            A += str(0)
        else:
            A += str(i)
    print(A)
    return

def examD():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}

    N, M, K = LI()
    uf = UnionFind(N)
    B = [0]*N
    for _ in range(M):
        a, b = LI()
        B[a-1] += 1
        B[b-1] += 1
        uf.unite(a-1,b-1)
    block = []
    for _ in range(K):
        c, d = LI()
        c -= 1
        d -= 1
        if uf.same(c,d):
            B[c] += 1
            B[d] += 1
    ans = [0]*N
    check = [-1]*N
    for i in range(N):
        root = uf.find(i)
        if check[root]==-1:
            size = uf.size(root)
            check[root] = size
        else:
            size = check[root]
        ans[i] += size-1
        ans[i] -= B[i]
        if ans[i]<0:
            ans[i] = 0
    #print(check)
    print(" ".join(map(str,ans)))
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
 
class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

N, M, K = map(int, input().split())
uf = Unionfind(N)
sub = [0]*N

for _ in range(M):
    A, B = map(int, input().split())
    uf.unite(A-1, B-1)
    sub[A-1] += 1
    sub[B-1] += 1
    
for _ in range(K):
    C, D = map(int, input().split())
    
    if uf.is_same(C-1, D-1):
        sub[C-1] += 1
        sub[D-1] += 1

for i in range(N):
    ans = uf.count(i)-1
    ans -= sub[i]
    
    if i<N-1:
        print(ans, end=' ')
    else:
        print(ans)

Submission status: Accepted

Solution code:
def main():
    class unionfind():
        # size:要素数,tree：unionfind木
        def __init__(self, size):  # self,要素数
            self.size = size
            self.tree_root = list(range(self.size))
            self.tree_depth = [1]*self.size
            self.tree_size = [1]*self.size

        # rootを探す
        def root(self, index):
            temp_list = []
            temp = self.tree_root[index]
            while index != temp:
                temp_list.append(index)
                index = temp
                temp = self.tree_root[index]
            for i in temp_list:
                self.tree_root[i] = index
            return index

        # 結合
        def unite(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 != r2:
                d1, d2 = self.tree_depth[r1], self.tree_depth[r2]
                if d1 <= d2:
                    self.tree_root[r1] = r2
                    self.tree_depth[r2] = max(d1+1, d2)
                    self.tree_size[r2] += self.tree_size[r1]
                else:
                    self.tree_root[r2] = r1
                    self.tree_depth[r1] = max(d2+1, d1)
                    self.tree_size[r1] += self.tree_size[r2]

        # 同じか判定
        def same(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            return r1 == r2

    n, m, k = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    cd = [list(map(int, input().split())) for _ in [0]*k]
    u = unionfind(n)

    for a, b in ab:
        u.unite(a-1, b-1)

    friend = [u.tree_size[u.root(i)]-1 for i in range(n)]

    for a, b in ab:
        friend[a-1] -= 1
        friend[b-1] -= 1
    for c, d in cd:
        if u.same(c-1, d-1):
            friend[c-1] -= 1
            friend[d-1] -= 1
    print(*friend)


main()

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    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 union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from collections import Counter

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

ds = DisjointSet(N)
deg = [0]*N
for _ in range(M):
    a,b = map(int,input().split())
    deg[a-1] += 1
    deg[b-1] += 1
    ds.union(a-1,b-1)

c = Counter(ds.find(i) for i in range(N))

res = [c[ds.find(i)]-deg[i]-1 for i in range(N)]
for _ in range(K):
    c,d = map(int,input().split())
    if ds.find(c-1) == ds.find(d-1):
        res[c-1] -= 1
        res[d-1] -= 1

print(*res)

Submission status: Accepted

Solution code:
class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

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

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

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True

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

import sys
input = sys.stdin.readline
N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uni = Union(N)
ans = [-1] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  ans[a] -= 1
  ans[b] -= 1

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

for i in range(N):
  ans[i] += uni.size(i)
  for j in L[i]:
    if uni.same(i, j):
      ans[i] -= 1

ans = map(str, ans)
print(" ".join(ans))

Submission status: Accepted

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

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

#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)]

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

num = [0]*n

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

edge = [[] for i in range(n)]

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


for i in range(n):
    cnt = size(i) - num[i] - 1
    for e in edge[i]:
        if same(e,i):
            cnt -= 1
    print(cnt,end=' ')