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
import math
import copy
import queue
input = sys.stdin.readline
n,m,k = map(int,input().split())
f = [[] for _ in range(n+1)]
b = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)
for _ in range(k):
    x,y = map(int, input().split())
    b[x].append(y)
    b[y].append(x)
g = [0 for _ in range(n+1)]
g_cnt = [0]
g_no = 0
for i in range(1,n+1):
    if g[i] > 0:
        continue

    g_no += 1
    q = queue.Queue()
    q.put(i)
    cnt = 0
    while not q.empty():
        g[i] = g_no
        node = q.get()
        cnt += 1
        for n_node in f[node]:
            if g[n_node] == 0:
                q.put(n_node)
                g[n_node] = g_no
    g_cnt.append(cnt)

for i in range(1,n+1):
    block = 0
    for x in b[i]:
        block += (g[i] == g[x])
    print (g_cnt[g[i]] - len(f[i]) - block - 1,end=' ')
print ()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

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

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if (x == y):
            return
        elif (self.size[x] > self.size[y]):
            self.size[x] += self.size[y]
            self.root[y] = x
        else:
            self.size[y] += self.size[x]
            self.root[x] = y

    def isSameGroup(self, x, y):
      return self.Find_Root(x) == self.Find_Root(y)

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

A = UnionFind(N)

F = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    F[a] += 1
    F[b] += 1
    A.Unite(a, b)
    
B = [0] * (N + 1)
for _ in range(K):
    c, d = map(int, input().split())
    if A.isSameGroup(c, d):
        B[c] += 1
        B[d] += 1
        
ans = []
for i in range(1, N + 1):
    size = A.size[A.Find_Root(i)]
    block = B[i]
    friends = F[i]
    res = size - block - friends - 1
    ans.append(str(res))

print(" ".join(ans))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = list(range(n + 1))
        self.size = [1] * (n + 1)

    def root(self, x: int) -> int:
        if self.par[x] == x: return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self, x: int, y: int):
        root_x, root_y = self.root(x), self.root(y)
        if root_x != root_y:
            if self.size[root_x] < self.size[root_y]:
                root_x, root_y = root_y, root_x
            self.size[root_x] += self.size[root_y]
            self.par[root_y] = root_x

    def check(self, x: int, y: int) -> bool:
        root_x, root_y = self.root(x), self.root(y)
        return root_x == root_y

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

u = UnionFind(N)

ABm = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    ABm[a] += 1
    ABm[b] += 1
    u.unite(a, b)
    
CDk = [0] * (N + 1)
for _ in range(K):
    c, d = map(int, input().split())
    if u.check(c, d):
        CDk[c] += 1
        CDk[d] += 1
        
ans = []
for i in range(1, N + 1):
    size = u.size[u.root(i)]
    block = CDk[i]
    friends = ABm[i]
    res = size - block - friends - 1
    ans.append(str(res))

print(" ".join(ans))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))    # self.par[x] = y: xの属する木の根はy
        self.siz = [1] * n

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.siz[x] > self.siz[y]:     # 小さい木を大きい木に接続（根までが近くなる）
            x, y = y, x
        self.siz[y] += self.siz[x]
        self.par[x] = y

    def tree_size(self, x):
        return self.siz[self.root(x)]


N, M, K = map(int, input().split())
F = UnionFind(N)
n_friend = [0] * N

B = {}
for i in range(N):
    B[i] = set()
for _ in range(M):
    p, q = map(int, input().split())
    n_friend[p - 1] += 1
    n_friend[q - 1] += 1
    F.unite(p - 1, q - 1)
for _ in range(K):
    p, q = map(int, input().split())
    B[p - 1].add(q - 1)
    B[q - 1].add(p - 1)


# calc friend candidate
i, blocked = 0, 0
for b in B[0]:
    if F.same(i, b):
        blocked += 1
print(F.tree_size(i) - 1 - n_friend[i] - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if F.same(i, b):
            blocked += 1
    print(F.tree_size(i) - 1 - n_friend[i] - blocked, end='')
print('')

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
par = list(range(N))
siz = [1] * N
n_friend = [0] * N


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


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


def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if siz[x] > siz[y]:
        x, y = y, x
    siz[y] += siz[x]
    par[x] = y


def tree_size(x):
    return siz[root(x)]


B = {}
for i in range(N):
    B[i] = set()
for _ in range(M):
    p, q = map(int, input().split())
    n_friend[p - 1] += 1
    n_friend[q - 1] += 1
    unite(p - 1, q - 1)
for _ in range(K):
    p, q = map(int, input().split())
    B[p - 1].add(q - 1)
    B[q - 1].add(p - 1)


# calc friend candidate
i, blocked = 0, 0
for b in B[0]:
    if same(i, b):
        blocked += 1
print(tree_size(i) - 1 - n_friend[i] - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if same(i, b):
            blocked += 1
    print(tree_size(i) - 1 - n_friend[i] - blocked, end='')
print('')

Submission status: Accepted

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

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

def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
            

def size(a):
    return siz[find(a)]

def same(a,b):
    return find(a)==find(b)

ans=[0 for i in range(N)]
for _ in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    union(A,B)
    ans[A]-=1
    ans[B]-=1
for i in range(N):
    ans[i]+=size(i)-1
for _ in range(K):
    C,D=map(int,input().split())
    C,D=C-1,D-1
    if(same(C,D)):
        ans[C]-=1
        ans[D]-=1
        
print(*ans)

Submission status: Accepted

Solution code:
import sys

line = sys.stdin.readline().strip()
n,m,k = map(int, line.split())
roots = [-1]*n
linked = [0]*n
def find_root(x):
    if roots[x] < 0:
        return x
    else:
        roots[x] = find_root(roots[x])
        return roots[x]
def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if (x==y):
        return
    if roots[x] > roots[y]:
        c, d = y,x
        x,y = c,d
    roots[x] += roots[y]
    roots[y] = x

for i in range(m):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c, d = a-1,b-1
    linked[c] += 1 
    linked[d] += 1
    unite(c,d)
#print(roots)
blacks = [[]for i in range(n)]
for i in range(k):
    line = sys.stdin.readline().strip()
    a,b = map(int, line.split())
    c,d = a-1, b-1
    blacks[c].append(d)
    blacks[d].append(c)
res = []
for i in range(n):
    r = -roots[find_root(i)] - 1 - linked[i]
    for one in blacks[i]:
        if find_root(one) == find_root(i):
            r -= 1
    res.append(r)
    
print (" ".join(map(str, res)))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

def find(parent, i):
   t = parent[i]
   if t < 0:
      return i
   t = find(parent, t)
   parent[i] = t
   return t

def unite(parent, i, j):
   i = find(parent, i)
   j = find(parent, j)
   if i == j:
      return
   parent[j] += parent[i]
   parent[i] = j

setrecursionlimit(10 ** 5)

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

parent = [-1] * n
friends = [[] for _ in range(n)]
for A, B in ab:
   unite(parent, A-1, B-1)
   friends[A-1].append(B-1)
   friends[B-1].append(A-1)

blocks = [[] for _ in range(n)]
for C, D in cd:
   blocks[C-1].append(D-1)
   blocks[D-1].append(C-1)

result = []
for i in range(n):
   p = find(parent, i)
   t = -parent[p] - 1
   t -= len(friends[i])
   for b in blocks[i]:
      if p == find(parent, b):
         t -= 1
   result.append(t)

print(*result)

Submission status: Accepted

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

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

def main():
  L = []
  n, m, k = map(int, input().split())
  uf = UnionFind(n+1)
  F = [[] for _ in range(n+1)]
  for _ in range(m):
    a, b = map(int, input().split())
    F[a].append(b)
    F[b].append(a)
    uf.unite(a, b)
  G = [set() for _ in range(n+1)]
  for _ in range(k):
    c, d = map(int, input().split())
    G[c].add(d)
    G[d].add(c)
  for i in range(1, n+1):
    temp = uf.size(i)
    temp -= len(F[i])
    for v in G[i]:
      if uf.same(i, v):
        temp -= 1
    L.append(temp-1)
  print(*L)
    
if __name__ == "__main__":
  main()

Submission status: Accepted

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

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n, m, k = map(int,input().split())
    E = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)
    block = [tuple(map(int,input().split())) for _ in range(k)]

    # connected component
    cnt = 0
    color = [None]*n
    def dfs(v)->bool:
        if color[v] is not None: return False
        stack = [v]
        while stack:
            v = stack.pop()
            color[v] = cnt
            for nv in E[v]:
                if color[nv] is not None: continue
                stack.append(nv)
        return True

    for v in range(n):
        cnt += dfs(v)

    C = Counter(color)
    res = [C[color[v]]-len(E[v])-1 for v in range(n)]
    # block 分を引く
    for u, v in block:
        u-=1; v-=1
        if color[u]==color[v]:
            res[u]-=1
            res[v]-=1
    print(*res)
resolve()

Submission status: Accepted

Solution code:
#n = int(input())
#s = input()
#n, k= map(int,input().split())
#da = list(map(int,input().split()))
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n
    def root(self, x):
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
    def unite(self, x, y):
        if self.root(x) == self.root(y):
            return
        if self.rank[x] > self.rank[y]:
            self.size[self.root(x)] += self.size[self.root(y)]
            self.par[self.root(y)] = self.root(x)
        else:
            self.size[self.root(y)] += self.size[self.root(x)]
            self.par[self.root(x)] = self.root(y)
        if self.rank[x] == self.rank[y]:
            self.rank[y]+=1
    def check(self, x, y):
        return self.root(x) == self.root(y)
    def sizeCheck(self, x):
        return self.size[self.root(x)]
    def len(self):
        return len(self.par)

n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0]*n
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    ans[a]-=1
    ans[b]-=1
co = [0]*n
for i in range(n):
    ans[i] += uf.sizeCheck(i)-1
for i in  range(k):
    c,d = map(int,input().split())
    if uf.check(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    if i == n-1:
        print(ans[i])
    else:
        print(ans[i],end=' ')

Submission status: Accepted

Solution code:
#n = int(input())
#s = input()
#n, k= map(int,input().split())
#da = list(map(int,input().split()))
class UnionFind:
    def __init__(self, n):
        self.size = n
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n
    def root(self, x):
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
    def unite(self, x, y):
        if self.root(x) == self.root(y):
            return
        if self.rank[x] > self.rank[y]:
            self.size[self.root(x)] += self.size[self.root(y)]
            self.par[self.root(y)] = self.root(x)
        else:
            self.size[self.root(y)] += self.size[self.root(x)]
            self.par[self.root(x)] = self.root(y)
        if self.rank[x] == self.rank[y]:
            self.rank[y]+=1
    def check(self, x, y):
        return self.root(x) == self.root(y)
    def sizeCheck(self, x):
        return self.size[self.root(x)]

n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0]*n
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    ans[a]-=1
    ans[b]-=1
co = [0]*n
for i in range(n):
    ans[i] += uf.sizeCheck(i)-1
for i in  range(k):
    c,d = map(int,input().split())
    if uf.check(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    if i == n-1:
        print(ans[i])
    else:
        print(ans[i],end=' ')

Submission status: Accepted

Solution code:
#n = int(input())
#s = input()
#n, k= map(int,input().split())
#da = list(map(int,input().split()))
class UnionFind:
    def __init__(self, n):
        self.size = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
    def root(self, x):
        if self.par[x] != x:
            self.par[x] = self.root(self.par[x])
        return self.par[x]
    def unite(self, x, y):
        if self.root(x) == self.root(y):
            return
        if self.rank[x] > self.rank[y]:
            self.par[self.root(y)] = self.root(x)
        else:
            self.par[self.root(x)] = self.root(y)
        if self.rank[x] == self.rank[y]:
            self.rank[x]+=1
    def check(self, x, y):
        return self.root(x) == self.root(y)

n,m,k = map(int,input().split())
uf = UnionFind(n)
ans = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    ans[a]-=1
    ans[b]-=1
co = [0 for i in range(n)]
for i in range(n):
    co[uf.root(i)]+=1
for i in range(n):
    ans[i] += co[uf.root(i)]-1
for i in  range(k):
    c,d = map(int,input().split())
    if uf.check(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
for i in range(n):
    if i == n-1:
        print(ans[i])
    else:
        print(ans[i],end=' ')

Submission status: Accepted

Solution code:
#見ながら､一応わかったつもり


def mi():return map(int,input().split())
#input
n,m,k=mi()
ab=[tuple(mi()) for _ in range(m)]
cd=[tuple(mi()) for _ in range(k)]


#class
class UnionFind:
  def __init__(self,n):
    self.parent=[i for i in range(n)]
    self.rank=[0]*n
    self.count=0
  def root(self,a):#rootを探す
    if self.parent[a]==a:
      return a
    else:
      self.parent[a]=self.root(self.parent[a])
      return self.parent[a]
  def is_same(self,a,b):#同じかどうか
    return self.root(a)==self.root(b)
  def unite(self,a,b):#根をまとめる
    ra=self.root(a)
    rb=self.root(b)
    if ra==rb:
      return
    if self.rank[ra]<self.rank[rb]:
      self.parent[ra]=rb
    else:
      self.parent[rb]=ra
    if self.rank[ra]==self.rank[rb]:
      self.rank[ra]+=1
      self.count+=1
      
            
uf=UnionFind(n)
friends=[0 for _ in range(n)]
blocks=[[] for _ in range(n)]


for a,b in ab:
  a=a-1
  b=b-1
  friends[a]+=1
  friends[b]+=1
  uf.unite(a,b)
  
  
for i in range(n):
  uf.root(i)
  
for c,d in cd:
  c-=1;d-=1
  blocks[c]+=d,
  blocks[d]+=c,
  
    
import collections 
ctr=collections.Counter()
for i in range(n):
  ctr[uf.parent[i]]+=1
  
  
ans=[0]*n
for i in range(n):
  tmp=ctr[uf.root(i)]-1-friends[i]
  for b in blocks[i]:
    if uf.is_same(i,b):
      tmp-=1
  ans[i]=tmp
print(*ans)

Submission status: Accepted

Solution code:
import collections
import sys

readline = sys.stdin.buffer.readline


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

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

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

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


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

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i in range(N):
        E.find(i)

    ll = collections.defaultdict(int)
    for i in E.par:
        ll[i] += 1

    for i in range(N):
        ans[i] += ll[E.par[i]] - 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1

    print(*ans)


main()

Submission status: Accepted

Solution code:
import collections
import itertools
import sys

readline = sys.stdin.buffer.readline


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

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

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

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


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

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i in range(N):
        E.find(i)

    ll = collections.defaultdict(int)
    for i in E.par:
        ll[i] += 1

    for i in range(N):
        ans[i] += ll[E.par[i]] - 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1

    print(*ans)


main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N
        self.size = [1 for i in range(N)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if (x == y):
            return
        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1
        return count
    def get_size(self, x):
        root = self.find(x)
        return self.size[root]
N,M,K = map(int,input().split())
U = UnionFind(N)
direct = [0 for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    U.unite(a,b)
    direct[a] += 1
    direct[b] += 1
neg = [0 for i in range(N)]
for i in range(K):
    c,d = map(int,input().split())
    c,d = c-1,d-1
    if U.same(c,d):
        neg[c] += 1
        neg[d] += 1
ans = []
for i in range(N):
    ans.append(U.get_size(i)-1-neg[i]-direct[i])
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    """
    素集合データ構造: 要素を素集合（互いに重ならない集合）に分割して管理するデータ構造
        Union: 2つの集合を1つに併合する
        Find: ある要素がどの集合に属しているかを判定する
    """

    def __init__(self, n):
        self.n = n
        # 各要素の親要素の番号を格納するリスト
        # 要素が根（ルート）の場合は[-そのグループの要素数]を格納する
        self.parents = [-1] * n

    def find(self, x):
        """
        要素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が属するグループと要素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):
        """
        要素xが属するグループのサイズ（要素数）を返す
        """
        return -self.parents[self.find(x)]

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

    def members(self, x):
        """
        要素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):
        """
        print()での表示用
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

uf = UnionFind(n)
friend = [set() for _ in range(n)]
block = [set() for _ in range(n)]

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

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c,d):
        block[c].add(d)
        block[d].add(c)

for i in range(n):
    print(uf.size(i) - len(friend[i]) - len(block[i]) - 1, end=' ')

Submission status: Accepted

Solution code:
slct='D'

# C
if slct=='C':
    N,M=map(int,input().split())
    cnd=[tuple(int(i) for i in input().split()) for j in range(M)]
    ans=-1
    for n in range(10**N):
        # print(n)
        flag=True
        n_str=str(n)
        if len(n_str)!= N:
            continue
        for s,c in cnd:
            if n_str[s-1]!=str(c):
                # print(n_str[s-1],c)
                flag=False
                break
        if flag:
            ans=n
            break
    print(ans)

# D
elif slct=='D':
    N,M,K=map(int,input().split())
    
    par=[-1 for _ in range(N)]
    # 負なら根でabsがその根の属する木のサイズ
    # 正ならその値が親

    def root(n):
        if par[n]<0:
            return n
        else:
            par[n]=root(par[n]) # 親の根に繋ぎなおす
            return par[n]
    
    def unite(m,n):
        x=root(m)
        y=root(n)
        if x==y: # 同じ木にいる
            return
        if par[x]>par[y]: # yのサイズの方が大きい:swap
            x,y=y,x 
        par[x]+=par[y] # サイズの大きいxにくっつける: サイズを記録
        par[y]=x 

    def issame(m,n):
        return root(m)==root(n)
    
    def size(n): # nの属する木のsizeを取得
        return -par[root(n)]
    
    # iの求めたい値 = size(i) -直接の友達関係の数 -iの木上でブロック関係にある数 -1
    # 直接の友達関係ならお互いに同じ木にいる
    ans=[-1 for _ in range(N)] # 自分の分: -1
    
    for _ in range(M): #木達の構築
        A,B=map(int,input().split())
        unite(A-1,B-1)
        # 直接の友達関係を引く
        ans[A-1]-=1
        ans[B-1]-=1
    for _ in range(K): # ブロック関係にあるかどうか
        C,D=map(int,input().split())
        #同じ木でなければ答えに関係ない,同じ木にいるなら引く
        if issame(C-1,D-1):
            ans[C-1]-=1
            ans[D-1]-=1
    for i in range(N): 
        print(ans[i]+size(i))

Submission status: Accepted

Solution code:
from collections import Counter
n, m, k = map(int, input().split())

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

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

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


friends = []
for i in range(n + 1):
    friends.append(UnionFind(i))

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

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


labels = [None] * (n + 1)
parents = [0] * (n + 1)
for i in range(1, n + 1):
    u = friends[i]
    parents[i] = u.get_root().val
CounterDict = Counter(parents)

for i in range(len(parents)):
    p = parents[i]
    labels[i] = [p, CounterDict.get(p)]

ans = []
for i in range(1, n + 1):
    num = labels[i][1] - 1
    for j in graph[i]:
        if labels[i][0] == labels[j][0]:
            num -= 1
    for k in block[i]:
        if labels[i][0] == labels[k][0]:
            num -= 1
    ans.append(num)
print(*ans)