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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

#Union Findデータ構造
class UnionFind:
    def __init__(self, n):
        #Data: 正:親要素のノード番号, 負:サイズ
        self.D = [-1 for i in range(n)]
    
    def find(self, x:int)->int:
        if self.D[x] < 0:
            return x
        else:
            self.D[x] = self.find(self.D[x])
            return self.D[x]

    
    def unite(self, x:int, y:int)->bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.D[x] > self.D[y]:
                self.D[x], self.D[y] = self.D[y], self.D[x]
            else:
                pass
            self.D[x] += self.D[y]
            self.D[y] = x
            return True

    def same(self, x:int, y:int)->bool:
        return self.find(x) == self.find(y)

    def size(self, x:int)->int:
        return -self.D[self.find(x)]

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

uf = UnionFind(n)  

CF = [0] * n #Count Friend
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    CF[a] += 1
    CF[b] += 1
    uf.unite(a, b)

CBinG = [0] * n #Count Block in Group
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d) == True:
        CBinG[c] += 1
        CBinG[d] += 1
    else:
        pass
    
for i in range(n):
    ans = uf.size(i) - 1 - CF[i] - CBinG[i]
    print(ans, end=' ')

Submission status: Accepted

Solution code:
class UnionFind:

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

    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 isSame(self, x, y):
        return self.find(x) == self.find(y)

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

        if self.d[x] > self.d[y]:
            self.p[x] += self.p[y]
            self.p[y] = x
        else:
            self.p[y] += self.p[x]
            self.p[x] = y
            if self.d[x] == self.d[y]:
                self.d[y] += 1

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


N, M, K = map(int, input().split())
n, u = {i: set() for i in range(N)}, UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    u.unite(A - 1, B - 1)
    n[A - 1].add(B - 1)
    n[B - 1].add(A - 1)
for _ in range(K):
    C, D = map(int, input().split())
    if u.isSame(C - 1, D - 1):
        n[C - 1].add(D - 1)
        n[D - 1].add(C - 1)

print(' '.join([str(u.size(i) - len(n[i]) - 1) for i in range(N)]))

Submission status: Accepted

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(4100000)

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

#友達関係
F = [[] for i in range(n)] #Friend
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
gid = 0 #group id

#DFSを行うための関数
def using_DFS(p):
    if G[p] == 0:
        G[p] = gid
        for j in F[p]:
            if G[j-1] == 0:
                using_DFS(j-1)
            else:   #すでに登場
                pass
    else:
        pass

for i in range(n):
    if G[i] == 0:
        gid += 1
        using_DFS(i)
    else:
        pass
#print('G=',G)
#print('S=',S)

#ブロック関係
BinG = [[] for i in range(n)] #Block in Group
for i in range(k):
    c, d = map(int, input().split())
    if G[c-1] == G[d-1]:
        BinG[c-1].append(d)
        BinG[d-1].append(c)
    else:
        pass
#print('F=',F)
#print('B=',B)

GS = Counter(G) #Group Size
for i in range(n):
    ans =  GS[G[i]] - 1 - len(F[i]) - len(BinG[i])
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    n, m, k = map(int, input().split())
    fgraph = [list() for i in range(n)]
    bgraph = [list() for i in range(n)]
    cgraph = [list() for i in range(n)]
    
    rks = [None] *n
    sys.setrecursionlimit(10**9)
    # r: どの連結成分に存在するかをメモするid
    def dfs(graph,s,r):
        if rks[s] is None:
            rks[s] = r
        for i in range(len(graph[s])):
            if rks[graph[s][i]-1] is not None:
                continue
            dfs(graph, graph[s][i]-1,r)

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

    # print(fgraph)
    #print(bgraph)
    # 連結成分に対してid的なindexをつける
    c = -1
    for i in range(n):
        if rks[i] is None:
            c += 1
            dfs(fgraph, i, c)
    
    for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)

    counter = Counter(rks)
    for i in range(n):
        # counter[rks[i]] 連結成分のサイズ
        # len(fgraph[i]) 友達の数
        # len(bgraph[i]) 連結成分内のブロックの数
        # 1 自分
        print(counter[rks[i]] - len(fgraph[i]) - len(bgraph[i]) - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

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

  def find(self,k):
    if self.data[k]<0:
      return k
    self.data[k]=self.find(self.data[k])
    return self.data[k]

  def size(self,k):
    return -self.data[self.find(k)]

def main():
  n,m,k=LI()
  uf=UnionFind(n)

  friends=[set() for _ in range(n)]
  for _ in range(m):
    a,b=LI()
    a-=1
    b-=1
    friends[a].add(b)
    friends[b].add(a)
    uf.unite(a,b)

  blocks=[set() for _ in range(n)]
  for _ in range(k):
    a,b=LI()
    a-=1
    b-=1
    blocks[a].add(b)
    blocks[b].add(a)

  # for i in range(n):
  #   print(uf.size(i),friends[i])

  ans=[0]*n
  for i in range(n):
    par=uf.find(i)
    _ans=uf.size(i)-1-len(friends[i])
    for x in blocks[i]:
      if par==uf.find(x):
        _ans-=1

    ans[i]=_ans

  return ' '.join([str(x) for x in ans])

# main()
print(main())

Submission status: Accepted

Solution code:
from collections import deque

N,M,K=map(int,input().split())
Sn=[0]*N
Sm=[0]*N
Sk=[0]*N
S=[0]*N

friend=[[] for _ in range(N)]
for i in range(M):#連結数,友達数
    A,B=map(int,input().split())
    Sm[A-1]+=1
    Sm[B-1]+=1
    
    friend[A-1].append(B-1)
    friend[B-1].append(A-1)



label=[-1]*N
for i in range(N):
    if label[i]==-1:
        label[i]=i
        F=deque(friend[i])
        while F:
            F0=F.pop()
            if label[F0]==-1:
                Sn[i]+=1
                label[F0]=i
                for ii in friend[F0]:
                    if label[ii]==-1:
                        F.append(ii)
    else:
        Sn[i]=Sn[label[i]]

for i in range(K):#ブロック数
    C,D=map(int,input().split())
    if label[C-1]==label[D-1]:
        Sk[C-1]+=1
        Sk[D-1]+=1

for i in range(N):
    S[i]=str(Sn[i]-Sm[i]-Sk[i])

print(' '.join(S))

Submission status: Accepted

Solution code:
#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}

#resultは、ある人が何人の友達候補を持つかを保持する。
result=[]
#friendGroupは、ある人が何グループに所属するかを保持する。
friendGroup=[]

#初期化
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)
    friendGroup.append(0)

#友達関係を作る
for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

#DFS
checked=set([])
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.add(i)
        group=set([i])
        bf=set([i])
        friendGroup[i-1]=i
        while len(group)!= 0:
            temp=group.pop()
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.add(item)
                    bf.add(item)
                    #誰がどのグループに所属するかを保持する
                    friendGroup[item-1]=i
        lenbf=len(bf)
        for item1 in bf:
            result[item1-1]=lenbf-1-len(list(friend[item1]))

#block関係を確認する
for _ in range(k):
    a,b=map(int,input().split())

    #block関係にあるペアが、同じfirendGroupだったらマイナス１する
    if friendGroup[a-1]!=0 and friendGroup[a-1]==friendGroup[b-1]:
        result[a-1]-=1
        result[b-1]-=1

result=list(map(str,result))
print(" ".join(result))

Submission status: Accepted

Solution code:
#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
friendGroup=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)
    friendGroup.append(0)

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

checked=set([])
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.add(i)
        group=set([i])
        bf=set([i])
        friendGroup[i-1]=i
        while len(group)!= 0:
            temp=group.pop()
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.add(item)
                    bf.add(item)
                    friendGroup[item-1]=i
        lenbf=len(bf)
        for item1 in bf:
            result[item1-1]=lenbf-1-len(list(friend[item1]))

for _ in range(k):
    a,b=map(int,input().split())
    if friendGroup[a-1]!=0 and friendGroup[a-1]==friendGroup[b-1]:
        result[a-1]-=1
        result[b-1]-=1

result=list(map(str,result))
print(" ".join(result))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_d
import sys

#Union Find
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)

n,m,k = map(int,input().split())
friend = [0 for _ in range(n)]
block = [[] for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    friend[a - 1]+=1
    friend[b - 1]+=1
    uf.union(a - 1,b - 1)
for i in range(k):
    c,d = map(int,input().split())
    block[c - 1].append(d - 1)
    block[d - 1].append(c - 1)

for i in range(n):
    ans = uf.size(i) - friend[i] - 1
    for b in block[i]:
        if uf.same(i,b):
            ans-=1
    sys.stdout.write(str(ans) + " ")
print("")

Submission status: Accepted

Solution code:
import sys

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N,M,K = map(int,input().split())
friend =[0]*N
block = {}
for i in range(N):
  block[i] = []
uf = UnionFind(N)
for i in range(M):
  a,b = map(int,input().split())  
  a -= 1;b-=1
  friend[a]+=1
  friend[b]+=1
  uf.union(a,b)
  
for i in range(K):
  c,d = map(int,input().split())
  c -= 1
  d -= 1
  block[c].append(d)
  block[d].append(c)
res = [0]*N
for i in range(N):
  ans = uf.size(i)-1-friend[i]
  for u in block[i]:
    if uf.same(i,u):
      ans -= 1
      
  res[i] = ans
  
print(*res)

Submission status: Accepted

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

n,m,k=map(int,input().split())
friends_cand = UnionFind(n)
not_cand = [0 for i in range(n)]

for i in range(m):
    a,b = map(int, input().split())
    a, b = a-1, b-1
    friends_cand.union(a,b)
    not_cand[a] +=1
    not_cand[b] +=1
for i in range(k):
    c,d = map(int, input().split())
    c, d = c-1, d-1
    if friends_cand.find(c) == friends_cand.find(d):
        not_cand[c] +=1
        not_cand[d] +=1

size = [0 for i in range(n)]
for i in range(n):
    size[friends_cand.find(i)]+=1

ans = []
for i in range(n):
    ans.append(size[friends_cand.find(i)] - not_cand[i] - 1)
print(*ans)

Submission status: Accepted

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

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

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

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

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


n, m, k = map(int, input().split())
friend_cand = UnionFind(n)
friend = {i: set() for i in range(n)}
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friend[a].add(b)
    friend[b].add(a)
    friend_cand.unite(a, b)
block = {i: set() for i in range(n)}
for _ in range(k):
    c, d = map(lambda x: int(x)-1, input().split())
    block[c].add(d)
    block[d].add(c)

res = []
for i in range(n):
    friend_cnt = len(friend[i])
    block_cnt = 0
    for k in block[i]:
        if friend_cand.same(i, k):
            block_cnt += 1
    res.append(friend_cand.size(i) - friend_cnt - block_cnt - 1)

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

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
par = [i for i in range(N)]
rank = [0 for _ in range(N)]

def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
def unite(x, y):
  x, y = root(x), root(y)
  if x != y:
    if rank[x] < rank[y]:
      par[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
F, B = [], []
for i in range(M):
  a, b = map(int, input().split())
  F.append([a-1, b-1])
  unite(a-1, b-1)
for i in range(N):
  par[i] = root(i)
for i in range(K):
  a, b = map(int, input().split())
  B.append([a-1, b-1])
D = {}
for i in par:
  if i in D:
    D[i] += 1
  else:
    D[i] = 1
p = [0 for _ in range(N)]
for i in range(N):
  p[i] = D[par[i]]
for i in range(M):
  p[F[i][0]] -= 1
  p[F[i][1]] -= 1
for i in range(K):
  l = B[i][:]
  if par[l[0]] == par[l[1]]:
    p[l[0]] -= 1
    p[l[1]] -= 1
for i in range(N):
  if i != N - 1:
    print(p[i] - 1, end = ' ')
  else:
    print(p[i] - 1)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]#親
        self.rank = [1]*n # 木の高さ <- unite()で併合する際に木が深くなるのを避ける
        self.size = [1]*n # size[i] は i を根とするグループのサイズ


    def find(self, x): # x の根を返す
        if self.parent[x] == x: #xが根そのもの
            return x
        else:
            self.parent[x] = self.find(self.parent[x]) #あるxの親は必ず根になる <- 経路圧縮
            return self.parent[x]


    def unite(self, x, y): # x, y の属する集合を併合する
        x = self.find(x)#xにxの根を代入
        y = self.find(y)#yにyの根を代入
        if x!=y:
            if self.rank[x]<self.rank[y]:#根がxのほうがyのほうより浅い木
                self.parent[x] = y #xの親がyになる
                self.size[y]+=self.size[x] #yのサイズがxのサイズ分大きくなる
            else:
                self.parent[y] = x
                self.size[x]+=self.size[y]
                if self.rank[x]==self.rank[y]: #どちらも同じ深さの時
                    self.rank[x]+=1 #1だけ深くなる
    

    def is_same(self, x, y): # x, y が同じ集合に属するか判定する
        return self.find(x)==self.find(y)

    def group_size(self, x): # x が属する集合の大きさを返す
        return self.size[self.find(x)]

person_num, friend_relation_num, block_relation_num = [int(n) for n in input().rstrip().split()]
#friend
A, B = [0]*friend_relation_num, [0]*friend_relation_num
#block
C, D = [0]*block_relation_num, [0]*block_relation_num

direct = [[] for _ in range(person_num)]#直接の友達、ブロックされている人を管理
uf = UnionFind(person_num)#UnionFindでは根の番号は0から

for i in range(friend_relation_num):
    A[i], B[i] = [int(n)-1 for n in input().rstrip().split()]#UnionFindの根の番号に合わせる
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])# 人A[i]と人B[i]を友達関係として繋ぐ

for i in range(block_relation_num):
    C[i], D[i] = [int(n)-1 for n in input().rstrip().split()]#UnionFindの根の番号に合わせる
    if uf.is_same(C[i], D[i]):
        direct[C[i]].append(D[i])
        direct[D[i]].append(C[i])
        # ブロックされていても他のグループなら処理してはいけない

answer = [0]*person_num
for i in range(person_num):
    answer[i] = uf.group_size(i) - len(direct[i]) -1 
    #i番目の人の友達候補は、その人が含まれる木のサイズから、
    # その人の直接の友達、ブロックされている人の数を引き、
    # 更に自分として-1する

print(*answer)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        # リンク情報　子→親の番号　親(根)→負のサイズ
        self.d=[-1 for i in range(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):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        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)]
n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(n)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")

Submission status: Accepted

Solution code:

class UnionFind():
    def __init__(self,n):
        # リンク情報　子→親の番号　親(根)→負のサイズ
        self.d=[-1 for i in range(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):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        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)]

n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(n)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1

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

for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")

Submission status: Accepted

Solution code:

class UnionFind():
    def __init__(self,n):
        # リンク情報　子→親の番号　親(根)→負のサイズ
        self.d=[-1 for i in range(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):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        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)]

n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(100005)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1

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

for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)

class UnionFind():
  def __init__(self, n):
    self.n = n
    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 all_group_members(self):
    return {r: self.members(r) for r in self.roots()}
  
  #print(uf)で根と要素のリストを文字列で返す
  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
  n, m, k = map(int, input().split())
  deg = [0]*n
  ans = [0]*n
  uf = UnionFind(n)
  for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.union(a, b)
  
  for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
      deg[c] += 1
      deg[d] += 1
  
  for i in range(n):
    ans[i] = uf.size(i) - 1 -deg[i]
  
  print(' '.join(map(str, ans)))
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import Counter

n, m, k = map(int, input().split())
friends = []
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friends.append((a - 1, b - 1))
    graph[a - 1].append(b - 1)
    graph[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)

class Union:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.rank = 0
        self.size = 1

    def get_root(self):
        n = self
        while n.parent != n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val


unions = []
for i in range(n):
    unions.append(Union(i))

for a, b in friends:
    x, y = unions[a], unions[b]
    if x.find_set() == y.find_set():
        continue
    x_root, y_root = x.get_root(), y.get_root()
    if x_root.rank == y_root.rank:
        y_root.parent = x_root
        x_root.rank += 1
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root
    size = x_root.size + y_root.size
    x_root.size = size
    y_root.size = size

d = {}
relation = []
for i in range(n):
    u = unions[i]
    parent = u.find_set()
    relation.append(parent)

parents = Counter(relation)
for i in range(n):
    p = relation[i]
    relation[i] = [p, parents.get(p)]

ans = []
for i in range(n):
    t = relation[i][1] - 1
    parent = relation[i][0]
    for j in graph[i]:
        if relation[j][0] == parent:
            t -= 1
    for k in block[i]:
        if relation[k][0] == parent:
            t -= 1
    ans.append(t)

print(*ans)

Submission status: Accepted

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

    def Find(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.Find(self.par[x])
        return self.par[x]

    def Union(self, x, y):
        x = self.Find(x)
        y = self.Find(y)
        if (x==y): 
            return False
        if (self.par[x]>self.par[y]):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True
    
    def isSameGroup(self, x, y):
        return self.Find(x)==self.Find(y)
    
    def Size(self, x):
        return self.par[self.Find(x)]*-1
    
    def PrintTree(self):
        return self.par

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

uf = UnionFind(N)
deg = [0]*N
ans = [0]*N
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.Union(a, b)

for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.isSameGroup(c, d):
        deg[c] += 1
        deg[d] += 1

for i in range(N):
    ans[i] = uf.Size(i)-1-deg[i]

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