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
input=sys.stdin.readline
n,m,k=map(int,input().split())
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)
friends=[[] for _ in range(n)]
blocks=[[] for _ in range(n)]
root=dict()
for i in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  friends[a-1].append(b-1)
  friends[b-1].append(a-1)
lis=uf.roots()
for i in lis:
  size=uf.size(i)
  root[i]=size-1
for i in range(k):
  c,d=map(int,input().split())
  if uf.same(c-1,d-1):
    blocks[c-1].append(d-1)
    blocks[d-1].append(c-1)
ans=[]
for i in range(n):
  ans.append(root[uf.find(i)]-len(blocks[i])-len(friends[i]))
print(*ans)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
a_m, b_m = [], []
c_k, d_k = [], []
def minus(x):
    return int(x)-1

friends_list = [[] for i in range(n)]
block_list = [[] for i in range(n)]
for i in range(m):
    a_m.append(0)
    b_m.append(0)
    a_m[i], b_m[i] = map(minus, input().split())
    friends_list[a_m[i]].append(b_m[i])
    friends_list[b_m[i]].append(a_m[i])
for i in range(k):
    c_k.append(0)
    d_k.append(0)
    c_k[i], d_k[i] = map(minus, input().split())
    block_list[c_k[i]].append(d_k[i])
    block_list[d_k[i]].append(c_k[i])

# どのグループに属しているかを返す
def find(x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if parents[x] > parents[y]:
        x, y = y, x
    parents[x] += parents[y]
    parents[y] = x
    return True

def union_size(x):
    return -parents[find(x)]

def blocks_in_union(x):
    count = 0
    for block in block_list[x]:
        if find(x) == find(block):
            count += 1
    return count

parents =[ -1 for i in range(n)]
for i in range(m):
    unite(a_m[i], b_m[i])
for i in range(n):
    print(union_size(i)-1-len(friends_list[i])-blocks_in_union(i), end=' ')

Submission status: Accepted

Solution code:
def root(parents, i):
    depth = 0
    while parents[i] != i:
        i = parents[i]
        depth += 1

    return i, depth

def isSame(parents, a, b):
    return root(parents,a)[0] == root(parents, b)[0]

def union(parents, size, a, b):
    pa, deptha = root(parents, a)
    pb, depthb = root(parents, b)
    if pa == pb: # already same group
        return
    if deptha < depthb:
        parents[pa] = pb
        size[pb] += size[pa]
    else:
        parents[pb] = pa
        size[pa] += size[pb]

def resolve():
    N, M, K = list(map(int, input().split()))
    parents = [i for i in range(N)]
    size = [1] * N
    ans = [0] * N

    for i in range(M):
        A, B = list(map(int, input().split()))
        ans[A-1] += 1
        ans[B-1] += 1
        union(parents, size, A-1, B-1)

    for i in range(N):
        pi = root(parents, i)[0]
        ans[i] = size[pi] - ans[i] -1 # eliminate friend count from candidate

    for i in range(K):
        A, B = list(map(int, input().split()))
        if isSame(parents, A-1, B-1):
            ans[A-1] -= 1
            ans[B-1] -= 1

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

resolve()

Submission status: Accepted

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

    def FindRoot(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.FindRoot(self.parents[x])
            return self.parents[x]
    
    def Union(self,x,y):
        x = self.FindRoot(x)
        y = self.FindRoot(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 isSame(self,x,y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self,x):
        return -self.parents[self.FindRoot(x)]

n,m,k = [int(x) for x in input().split()]
obj = UnionFind(n)
cnt = [0]*(n+1)
for _ in range(m):
    a,b = [int(x) for x in input().split()]
    obj.Union(a,b)
    cnt[a] += 1
    cnt[b] += 1
for _ in range(k):
    c,d = [int(x) for x in input().split()]
    if obj.isSame(c,d):
        cnt[c] += 1
        cnt[d] += 1
ans = 0
for i in range(1,n+1):
    ans = obj.Size(i)-1-cnt[i]
    print(ans,end=" ")

Submission status: Accepted

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


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

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

    def unite(self, x, y):
        xd = self.find(x)
        yd = self.find(y)
        if(xd == yd):
            return False
        if self.d[xd] > self.d[yd]:
            self.d[yd] += self.d[xd]
            self.d[xd] = yd
        else:
            self.d[xd] += self.d[yd]
            self.d[yd] = xd
        return True

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

    def size(self, x):
        return -1 * self.d[self.find(x)]


def main():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    fr = [0] * n
    bl = [[] for _ in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        fr[a] += 1
        fr[b] += 1
        uf.unite(a, b)
    for i in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        bl[c].append(d)
        bl[d].append(c)

    ans = [0]*n
    for i in range(n):
        t = uf.size(i)-1-fr[i]
        for j in range(len(bl[i])):
            if(uf.same(i, bl[i][j])):
                t -= 1
        ans[i] = t
    print(*ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import time
n,m,k = map(int,input().split())
fr = defaultdict(set)
bl = []
start = time.time()
group = [0] * n
 
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  fr[a].add(b)
  fr[b].add(a)
 
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  bl.append((a,b))
 
 
g_num = 0
for i in range(n):
    if group[i] != 0:
        continue
    g_num += 1
    unvisited = set({i})
    while len(unvisited) > 0:
        v = unvisited.pop()
        group[v] = g_num
        for w in fr[v]:
            if group[w] > 0 or w in unvisited:
                continue
            unvisited.add(w)
 
group_size = defaultdict(int)
for x in group:
    group_size[x] += 1
 
bl_in_group = [0] * n
for a,b in bl:
    if group[a] == group[b]:
        bl_in_group[a] += 1
        bl_in_group[b] += 1
 
for i in range(n):
    print(group_size[group[i]] - len(fr[i]) - bl_in_group[i] - 1, end=' ')
 
print()

Submission status: Accepted

Solution code:
from collections import defaultdict
import time
n,m,k = map(int,input().split())
fr = defaultdict(set)
bl = []
start = time.time()
group = [0] * n

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

for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  bl.append((a,b))


g_num = 0
for i in range(n):
    if group[i] != 0:
        continue
    g_num += 1
    unvisited = set({i})
    while len(unvisited) > 0:
        v = unvisited.pop()
        group[v] = g_num
        for w in fr[v]:
            if group[w] > 0 or w in unvisited:
                continue
            unvisited.add(w)

group_size = defaultdict(int)
for x in group:
    group_size[x] += 1

bl_in_group = [0] * n
for a,b in bl:
    if group[a] == group[b]:
        bl_in_group[a] += 1
        bl_in_group[b] += 1

for i in range(n):
    print(group_size[group[i]] - len(fr[i]) - bl_in_group[i] - 1, end=' ')

print()

Submission status: Accepted

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

n,m,k = map(int,input().split())
ans = [0]*n
frd = [[] for _ in range(n)]

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

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

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

for i in range(n): 
    ans[i] += cnt[uni[i]] - 1
    print(ans[i],end=" ")

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return False
        if self.parents[x] > self.parents[y]: x,y = y,x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True
    
    # 根が同じか？
    def same(self, x , y):
        return self.find(x) == self.find(y)

    # 属するUnionの要素数
    def size(self, x):
        return -self.parents[self.find(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)]

# 初期化
uf = UnionFind(n)
# くっつける
for a,b in ab: uf.unite(a-1,b-1)

# 自身を引く(-1)
ans = [uf.size(i)-1 for i in range(n)]

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parents = [i for i in range(N)]
        self.sizes = [1] * N

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx < ry:
            self.parents[ry] = rx
            self.sizes[rx] += self.sizes[ry]
            self.sizes[ry] = 0
        elif rx > ry:
            self.parents[rx] = ry
            self.sizes[ry] += self.sizes[rx]
            self.sizes[rx] = 0

    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def size(self, x):
        return self.sizes[self.root(x)]

N, M, K = list(map(int, input().split()))
AB_list = []
for _ in range(M):
    A, B = list(map(int, input().split()))
    AB_list.append([A - 1, B - 1])
CD_list = []
for _ in range(K):
    C, D = list(map(int, input().split()))
    CD_list.append([C - 1, D - 1])

uf = UnionFind(N)
for A, B in AB_list:
    uf.unite(A, B)

friends = [0] * N
for A, B in AB_list:
    friends[A] += 1
    friends[B] += 1
blocks = [0] * N
for C, D in CD_list:
    if uf.root(C) != uf.root(D):
        continue
    blocks[C] += 1
    blocks[D] += 1
answers = [0] * N
for i in range(N):
    answers[i] = uf.size(i) - 1 - friends[i] - blocks[i]

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

Submission status: Accepted

Solution code:
#計算時間が足りない　何がダメなのか　工夫が足りない　研究が必要
from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = [0]*N
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]
seenb = [False for _ in range(N)]
def dfs():
    labelb = 1
    #while False in seen:
    for i in range(N):
        if seen[i] != False: continue
        label = 1
        #i = seen.index(False)
        seen[i] = label
        seenb[i] = labelb
        que = deque([i])
        seg = deque([i])
        while que:
            #print(que)
            neci = que.pop()
            for nec in graph[neci]:
                if seen[nec]== False:
                    seen[nec]=label
                    seenb[nec]=labelb
                    que.append(nec)
                    seg.append(nec)
                    label += 1
        for iii in seg:
            seen[iii] = label

        labelb += 1

dfs()
for i in range(N):
    count = seen[i] - 1 -len(graph[i])
    if bgraph[i] and seen[i]>=2:
          for j in bgraph[i]:
                if seenb[i] == seenb[j]:
                    count -= 1
    cnt[i]=count
print(*cnt)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10000)

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 resolve():
    N, M, K = map(int, input().split())
    A = [0]*M
    B = [0]*M
    for i in range(M):
        A[i], B[i] = map(int, input().split())
    C = [0]*K
    D = [0]*K
    for i in range(K):
        C[i], D[i] = map(int, input().split())

    uf = UnionFind(N)
    for a, b in zip(A, B):
        uf.union(a-1, b-1)

    direct_friends_num = [0]*N
    for a, b in zip(A, B):
        direct_friends_num[a-1] += 1
        direct_friends_num[b-1] += 1
    blocked_num = [0]*N
    for c, d in zip(C, D):
        if uf.find(c-1) == uf.find(d-1):
            blocked_num[c-1] += 1
            blocked_num[d-1] += 1

    ans = [0]*N
    for i in range(N):
        ans[i] = uf.size(i) - direct_friends_num[i] - blocked_num[i] - 1
    print(*ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
class UnionFindTree():
  def __init__(self,n):
    self.parent = []
    self.rank = []
    self.candidate = []
    for i in range(n):
      self.parent.append(i)
      self.rank.append(int(1))
      self.candidate.append(int(1))

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

  def unite(self,n,m):
    n = self.find(n)
    m = self.find(m)

    if n == m:
      return
    else:
      if self.rank[n] < self.rank[m]:
        self.parent[n] = m
        self.candidate[m] += self.candidate[n]
      elif self.rank[n] > self.rank[m]:
        self.parent[m] = n
        self.candidate[n] += self.candidate[m]
      elif self.rank[n] == self.rank[m]:
        self.parent[m] = n
        self.candidate[n] += self.candidate[m]
        self.rank[n] += 1




N,M,K = (int(i) for i in input().split())

uft = UnionFindTree(N)

friend = [0] * N
for i in range(M):
  A,B = (int(i) for i in input().split())
  uft.unite(A-1,B-1)
  friend[A-1] += 1
  friend[B-1] += 1


# candidate = [4,3,1]
# candidate => 自分 + 友達 + 友達候補 (include ブロック関係)
candidate = []
for i in range(N):
  candidate.append(uft.candidate[uft.find(i)])

blocked = [0] * N
for i in range(K):
  C,D = (int(i) for i in input().split())
  if uft.parent[C-1] == uft.parent[D-1]:
    blocked[C-1] += 1
    blocked[D-1] += 1

for i in range(N):
  candidate[i] -= (friend[i]+blocked[i]+1)


print(*candidate)

Submission status: Accepted

Solution code:
import numpy as np

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

    def find(self,x):#根を探す
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):
        return self.find(x)==self.find(y)

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

        if self.rank[x]>=self.rank[y]:
            self.par[y]=x
        else:
            self.par[x]=y
        if self.rank[x]==self.rank[y]:
            self.rank[x]+=1
        self.size[x]=self.size[y]=self.size[x]+self.size[y]
    
    def rev_size(self,n):
        for i in range(n+1):
            self.size[i]=self.size[self.find(i)]

    def dame_cnt(self,a,b):
        if a!=b:
            self.dame[a]+=1
            self.dame[b]+=1

N,M,K=map(int,input().split())#N：人の数、M：友達関係の数　：

UF=UnionFind(N)

for _ in range(M):
    A,B=map(int,input().split())
    UF.dame_cnt(A,B)
    if UF.same_check(A,B)==0:
        UF.union(A,B)

for _ in range(K):
    C,D=map(int,input().split())
    if UF.same_check(C,D):
        UF.dame_cnt(C,D)

UF.rev_size(N)

print(*list(np.array(UF.size[1:])-np.array(UF.dame[1:])-np.array([1]*(N))))

Submission status: Accepted

Solution code:
class UnionFind:
    """
    parents: 各要素の親要素
             要素がrootの場合には　-(そのグループに属する要素数) を格納
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        # xが属するグループのrootを取得
        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())

union_find = UnionFind(n)
friends_counter = {i: 0 for i in range(n)}
blocks_counter = {i: 0 for i in range(n)}

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

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

result = []
for i in range(n):
    result.append(str(union_find.size(i) - friends_counter[i] - blocks_counter[i] - 1))

print(" ".join(result))

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
graph = {i: set() for i in range(1, N + 1)}
banned = {i: set() for i in range(1, N + 1)}

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)

# BFS
group = {i: -1 for i in range(1, N + 1)}
count = {i: 0 for i in range(1, N + 1)}
for i in range(1, N + 1):
    if group[i] >= 0:
        continue
    queue = [i]
    group[i] = i
    count[i] += 1
    while queue:
        new = []
        for cur in queue:
            for nxt in graph[cur]:
                if group[nxt] == -1:
                    group[nxt] = group[cur]
                    count[group[nxt]] += 1
                    new.append(nxt)
        queue = new

res = [0] * N
# Remove itself
for i in range(N):
    res[i] = count[group[i + 1]] - 1

# Remove friends and blocked users
for i in range(N):
    for j in banned[i + 1]:
        if group[i + 1] == group[j]:
            res[i] -= 1
    for j in graph[i + 1]:
        if group[i + 1] == group[j]:
            res[i] -= 1
print(*res)

Submission status: Accepted

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードを示す。負は自身が親ということ。親だった場合は−(その集合のサイズ)
        self.parent = [-1] * N

    def root(self, A):
        # Aがどのグループに属しているか調べる
        # ノード番号を受けとって一番上の親ノードの番号を返す
        # print(A)
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        # 自分のいるグループの頂点数を調べる
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # AとBをくっつける
        # AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False  # すでにくっついてるからくっつけない

        if self.size(A) < self.size(B):
            # 大きい方(A)に小さいほう(B)をくっ付けたい
            # 大小が逆だったらひっくり返しちゃう。
            A, B = B, A

        # Aのサイズを更新する
        self.parent[A] += self.parent[B]
        # Bの親をAに変更する
        self.parent[B] = A

        return True

    def same(self, A, B):
        return self.root(A) == self.root(B)


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


uf = UnionFind(N)
# frd = [0] * N  # 友達の数

frd = defaultdict(int)

blk = [[] for _ in range(N)]  # ブロック関係。隣接リスト
ans = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frd[a] += 1
    frd[b] += 1
    uf.unite(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    blk[a].append(b)
    blk[b].append(a)
for i in range(N):
    ans[i] = uf.size(i) - 1 - frd[i]
    for j in blk[i]:
        if uf.same(i, j):
            ans[i] -= 1  # 同じグループ内でのblock関係を引く
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードを示す。負は自身が親ということ。親だった場合は−(その集合のサイズ)
        self.parent = [-1] * N

    def root(self, A):
        # Aがどのグループに属しているか調べる
        # ノード番号を受けとって一番上の親ノードの番号を返す
        # print(A)
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        # 自分のいるグループの頂点数を調べる
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # AとBをくっつける
        # AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False  # すでにくっついてるからくっつけない

        if self.size(A) < self.size(B):
            # 大きい方(A)に小さいほう(B)をくっ付けたい
            # 大小が逆だったらひっくり返しちゃう。
            A, B = B, A

        # Aのサイズを更新する
        self.parent[A] += self.parent[B]
        # Bの親をAに変更する
        self.parent[B] = A

        return True

    def same(self, A, B):
        return self.root(A) == self.root(B)


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


uf = UnionFind(N)
frd = [0] * N  # 友達の数
blk = [[] for _ in range(N)]  # ブロック関係。隣接リスト
ans = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frd[a] += 1
    frd[b] += 1
    uf.unite(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    blk[a].append(b)
    blk[b].append(a)
for i in range(N):
    ans[i] = uf.size(i) - 1 - frd[i]
    for j in blk[i]:
        if uf.same(i, j):
            ans[i] -= 1 # 同じグループ内でのblock関係を引く
print(*ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(6500)

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]
d=[-1]*N

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]
def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def same(a,b):
    if find(a)==find(b):return True
    else:return False


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

for i in range(K):
    a,b=map(int,input().split())
    B[a-1].append(b-1)
    B[b-1].append(a-1)

ans=[0]*N
for i in range(N):
    p=find(i)
    ans[i]=-d[p]-len(F[i])-1
    for b in B[i]:
        if same(i,b):
            ans[i]-=1
for i in ans:
    print(str(i),end=" ")

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def size(self, x):
        return -self.parent[self.root(x)]

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

tree = UnionFind(n)

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

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

for i in range(n):
    ret = tree.size(i)
    s = set()
    for j in friends[i]:
        s.add(j)
    for j in blocks[i]:
        if tree.same(i, j):
            s.add(j)
    ret -= len(s)
    print(ret-1)

Submission status: Accepted

Solution code:
from collections import deque

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

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n)]
    
    def find_root(self, n):
        if self.par[n] < 0:
            return n
        else:
            self.par[n] = self.find_root(self.par[n])
            return self.par[n]

    def union(self, n_1, n_2):
        par_1 = self.find_root(n_1)
        par_2 = self.find_root(n_2)
        if par_1 == par_2:
            return
        else:
            if self.par[par_1] <= self.par[par_2]:
                self.par[par_1] += self.par[par_2]
                self.par[par_2] = par_1
            else:
                self.par[par_2] += self.par[par_1]
                self.par[par_1] = par_2

if __name__ == "__main__":
    ans = []
    unionfind = UnionFind(N)
    friend = [[] for _ in range(N)]
    for _ in range(M):
        a_i, b_i = map(int, input().split())
        a_i -= 1
        b_i -= 1
        unionfind.union(a_i, b_i)
        friend[a_i].append(b_i)
        friend[b_i].append(a_i)
    block = [[] for _ in range(N)]
    for i in range(K):
        c_i, d_i = map(int, input().split())
        c_i -= 1
        d_i -= 1
        block[c_i].append(d_i)
        block[d_i].append(c_i)
    for i in range(N):
        block_sum = 0
        for block_user in block[i]:
            if unionfind.find_root(i) == unionfind.find_root(block_user):
                block_sum += 1
        ans.append(str(unionfind.par[unionfind.find_root(i)] * -1 -1 - len(friend[i]) - block_sum))
        
    print(" ".join(ans))