Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:
from collections import deque
N,M,K=map(int,input().split())
friend=[deque([]) for _ in range(N+1)]
block=[deque([]) for _ in range(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)
stack=deque()
group=[-1]*(N+1)
visited=[-1]*(N+1)
dic={}
for i in range(1,N+1):
  stack.append(i)
  main=i
  cnt=0
  while len(stack)>0:
    now=stack.popleft()
    if group[now]!=-1:
        continue
    stack.extend(friend[now])
    group[now]=main
    cnt+=1
  if cnt!=0:
    dic[main]=cnt

for i in range(1,N+1):
  ans=dic[group[i]]
  ans-=1
  ans-=len(friend[i])
  for j in block[i]:
    if group[j]==group[i]:
      ans-=1
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M, K = map(int,input().split())
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)

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

whatgroup = [-1 for _ in range(N+1)]
visited = [-1] * (N+1)
d = deque()
leaderdic = {}
for person in range(1,N+1):
    d.append(person)
    leader = person
    cnt = 0
    while len(d)>0:
        nowwho = d.popleft()
        if whatgroup[nowwho] != -1:
            continue
        d.extend(friendlist[nowwho])
        whatgroup[nowwho] = leader
        cnt += 1
    if cnt != 0:
        leaderdic[leader] = cnt
for person in range(1,N+1):
    ans = leaderdic[whatgroup[person]]
    ans -= 1
    ans -= len(friendlist[person])
    for block in blocklist[person]:
        if whatgroup[person]==whatgroup[block]:
            ans -= 1
    print(ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  sys.setrecursionlimit(10**5+10)
  N, M, K = map(int,input().split())
  class UnionFind:
      def __init__(self, N):
          self.par = [-1 for i in range(N+1)]
          self.rank = [1]*(N+1)

      def find(self, x):
          if self.par[x] < 0:
              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[x] += self.par[y]
              self.par[y] = x
          else:
              self.par[y] += self.par[x]
              self.par[x] = y
              if self.rank[x] == self.rank[y]:
                  self.rank[x] += 1

  UF = UnionFind(N)
  friendlist = [[] for _ in range(N+1)]
  for n in range(M):
      A, B = map(int,input().split())
      friendlist[A].append(B)
      friendlist[B].append(A)
      if not UF.same_check(A,B):
          UF.union(A, B)
  blocklist = [[] for _ in range(N+1)]
  for n in range(K):
      C, D = map(int, input().split())
      blocklist[C].append(D)
      blocklist[D].append(C)

  for person in range(1,N+1):
      root = UF.find(person)
      ans = -UF.par[root]-1
      ans -= len(friendlist[person])
      for l in blocklist[person]:
          if UF.same_check(person,l):
              ans -= 1
      print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+10)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            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[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
        
n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    friends[a] += 1
    friends[b] += 1
for k in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d):
        blocks[c] += 1
        blocks[d] += 1
    

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

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  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # 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, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            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 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)]


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M  # 入力時に 0-index に合わせる
C, D = [0] * K, [0] * K  # 入力時に 0-index に合わせる

direct =[[] for _ in range(N)]  # 同じ集合の友達もしくはブロック関係の人
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

for i in range(K):
    C[i], D[i] = map(int, input().split())
    C[i] -= 1
    D[i] -= 1
    if uf.is_same(C[i], D[i]):
        direct[C[i]].append(D[i])
        direct[D[i]].append(C[i])

ans = [0] * N
for i in range(N):
    ans[i] = uf.group_size(i) - len(direct[i]) - 1
print(*ans)

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:
n,m,k= map(int,input().split())
par = [-1]*n
def findsize(x):
    temp = par[x]
    if temp<0:return -1*temp
    else:return findsize(temp)
def find(x):
    if par[x]<0:return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    px,py=find(x),find(y)
    if px==py:return False
    else:
        if px<py:px,py=py,px
        par[px]+=par[py]
        par[py]=px
        return True
fl = []
for i in range(m):
    a,b= map(int,input().split())
    unite(a-1,b-1)
    fl.append((a-1,b-1))
bl = []
for i in range(k):
    c,d= map(int,input().split())
    bl.append((c-1,d-1))
points=[0]*n
for i in range(n):points[i]=findsize(find(i))-1
for i in range(m):
    (a1,b1)=fl[i]
    points[a1]-=1
    points[b1]-=1
for i in range(k):
    (c1,d1)=bl[i]
    if find(c1)==find(d1):
        points[c1]-=1
        points[d1]-=1
print(*points)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

class UnionFind():
        def __init__(self, n):
            self.parents = list(range(n))
            self.size = [1] * n
    
        def find(self, x):
            if self.parents[x] == x:
                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:
                if self.size[x] < self.size[y]:
                    x, y = y,x
                self.parents[y] = x
                self.size[x] += self.size[y]

def main():
    N, M, K = map(int, input().split())
    friend_adj = [[] for _ in range(N)]
    block_adj = [[] for _ in range(N)]
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        friend_adj[a].append(b)
        friend_adj[b].append(a)
        uf.union(a,b)
    for _ in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        if uf.find(c) == uf.find(d):
            friend_adj[c].append(d)
            friend_adj[d].append(c)

    ans = [uf.size[uf.find(i)]-1 for i in range(N)]

    for i in range(N):
        ans[i] -= len(friend_adj[i])        
        # for b in block_adj[i]:
        #     if uf.find(b) == uf.find(i):
        #         ans[i] -= 1
    print(*ans)
    
    
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

class UnionFind():
        def __init__(self, n):
            self.parents = list(range(n))
            self.size = [1] * n
    
        def find(self, x):
            if self.parents[x] == x:
                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:
                if self.parents[x] > self.parents[y]:
                    x, y = y,x
                self.parents[y] = x
                self.size[x] += self.size[y]

def main():
    N, M, K = map(int, input().split())
    friend_adj = [[] for _ in range(N)]
    block_adj = [[] for _ in range(N)]
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        friend_adj[a].append(b)
        friend_adj[b].append(a)
        uf.union(a,b)
    for _ in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        if uf.find(c) == uf.find(d):
            friend_adj[c].append(d)
            friend_adj[d].append(c)

    ans = [uf.size[uf.find(i)]-1 for i in range(N)]

    for i in range(N):
        ans[i] -= len(friend_adj[i])        
        # for b in block_adj[i]:
        #     if uf.find(b) == uf.find(i):
        #         ans[i] -= 1
    print(*ans)
    
    
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n , m , k = map(int, input().split())
r = [[] for i in range(n)]
bk = [[] for i in range(n)]
for i in range(m):
    a , b = map(int, input().split())
    r[a-1].append(b-1)
    r[b-1].append(a-1)
for i in range(k):
    c , d = map(int, input().split())
    bk[c-1].append(d-1)
    bk[d-1].append(c-1)


v=[0]*n
l=[0]*n
w=[0]*n

def dfs(now,c):
    global ln
    if v[now]==1:
        return
    v[now]=1
    ln+=1
    w[now]=c
    l[c]=ln
    for i in r[now]:
        dfs(i,c)
    return

for i in range(n):
    ln=0
    dfs(i,i)

ans =[]
for i in range(n):
    d=0
    for j in bk[i]:
        if w[j]==w[i]:
            d+=1
    ans.append(str(l[w[i]]-1-d-len(r[i])))
print(' '.join(ans))

Submission status: Accepted

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

g = [[] for i in range(n+1)]
f = [0]*(n+1)
b = []
for i in range(m):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)
  f[u] += 1
  f[v] += 1
for i in range(k):
  b.append(map(int, input().split()))
count = 0
renketu_list = [-1]*(n+1)
renketu_size = [0]
stack = []
for i in range(1, n+1):
  if renketu_list[i] == -1:
    count += 1
    renketu_list[i] = count
    renketu_size.append(1)
    while len(g[i]) > 0:
      stack.append(g[i].pop())
    while len(stack) > 0:
      v=stack.pop()
      if renketu_list[v] == -1:
        renketu_list[v] = count
        renketu_size[count] += 1
        while len(g[v])>0:
          stack.append(g[v].pop())

s = [0] * (n+1)
for i in range(1, n+1):
  s[i] += renketu_size[renketu_list[i]] - f[i] - 1
  
for i in range(k):
  u, v = b[i]
  if renketu_list[u] == renketu_list[v]:
    s[u] -= 1
    s[v] -= 1

print(" ".join(list(map(str, s[1:]))))

Submission status: Accepted

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

  def union(self, x, y):
    p1,p2 = self.find(x), self.find(y)
    if p1 == p2: return

    if self.par[p1] > self.par[p2]:
      p1,p2 = p2,p1
    self.par[p1] += self.par[p2]
    self.par[p2] = p1

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

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

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

N,M,K = map(int,input().split())
uf = UF(N)
adj = [ [] for _ in range(N)]
for _ in range(M):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append(v)
  adj[v].append(u)
  uf.union(u,v)

res = []
for n in range(N):
  res.append(uf.size(n) - 1 - len(adj[n]))

for _ in range(K):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  if uf.same(u,v):
    res[u] -= 1
    res[v] -= 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def inp():
        n, m = map(int, input().split())
        return n - 1, m - 1

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 rem(cand, p, q):
    cand[p] += 1
    cand[q] += 1

n, m, k = map(int, input().split())
UF = UnionFind(n)
non_cand = [1] * n
for _ in range(m):
    a, b = inp()
    UF.union(a, b)
    rem(non_cand, a, b)
for _ in range(k):
    c, d = inp()
    if UF.same(c, d):
        rem(non_cand, c, d)

ans = [UF.size(i) - non_cand[i] for i in range(n)]

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n , m , k = map(int,input().split())
tomo = [set() for i in range(n+1)]
to = [0 for i in range(n+1)]
bro = [set() for i in range(n+1)]
for i in range(m):
    a , b = map(int,input().split())
    tomo[a].add(b)
    tomo[b].add(a)
    to[a] += 1
    to[b] += 1
for i in range(k):
    c , d = map(int,input().split())
    bro[c].add(d)
    bro[d].add(c)

visit = [True for i in range(n+1)]
kurasuta = []
for i in range(1,n+1):
    if visit[i]:
        kar = {i}
        d = deque()
        d.append(i)
        cou = 1
        visit[i] = False
        while d:
            now = d.popleft()
            for j in tomo[now]:
                if visit[j]:
                    visit[j] = False
                    kar.add(j)
                    d.append(j)
                    cou += 1
        kurasuta.append([kar,cou])
    else:
        continue
ans = [0 for i in range(n)]

for i in range(len(kurasuta)):
    for j in kurasuta[i][0]:
        ans[j-1] = kurasuta[i][1] - to[j] - 1 - len(kurasuta[i][0] & bro[j])

print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    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)

edge1 = []
edge2 = []
for i in range(M):
    a,b = map(int,input().split())
    edge1.append((a-1,b-1))
for i in range(K):
    c,d = map(int,input().split())
    edge2.append((c-1,d-1))
for a,b in edge1:
    uf.union(a,b)

#同じグループに属する人数（自分を除く）    
ans = [uf.size(i)-1 for i in range(0,N)]

for a,b in edge1:#すでに友達なら削る
    ans[a] -= 1
    ans[b] -= 1

for c,d in edge2:
    if uf.same(c,d): #ブロック関係かつ同じグループに属しているなら
        ans[c] -= 1
        ans[d] -= 1
print(*ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m,k=map(int,input().split())
uf=UnionFind(n)
fr=[set() for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    fr[a-1].add(b-1)
    fr[b-1].add(a-1)
    uf.union(a-1,b-1)
br=[set() for _ in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    br[a-1].add(b-1)
    br[b-1].add(a-1)
ans=[0]*n
for i in range(n):
    t=uf.size(i)-len(fr[i])-1
    for j in br[i]:
        if uf.same(i,j):
            t-=1
    ans[i]=t
print(*ans)

Submission status: Accepted

Solution code:
def solve(n, m, k, a, b, c, d):
    V = range(1,n+1)
    parents = {x:x for x in V}
    def root(x):
        return x if x == parents[x] else root(parents[x])
    friends = {x:0 for x in V}
    for i in range(m):
        x, y = a[i], b[i]
        friends[x] += 1
        friends[y] += 1
        x = root(x)
        y = root(y)
        if x > y:
            x, y = y, x
        parents[y] = x
    group = {x:0 for x in V}
    for x in V:
        group[root(x)] += 1
    blocks = {x:0 for x in V}
    for i in range(k):
        x = root(c[i])
        y = root(d[i])
        if x == y:
            blocks[c[i]] += 1
            blocks[d[i]] += 1
    res = [group[root(x)] - friends[x] - blocks[x] - 1 for x in V]
    return " ".join(map(str, res))

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())
print(solve(n, m, k, a, b, c, d))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**20)
n, m, k = map(int, input().split())
ab = []
for _ in range(m):
    ab.append([int(x)-1 for x in input().split()])
cd = []
for _ in range(k):
    cd.append([int(x)-1 for x in input().split()])
group = [-1 for _ in range(n)]
lis = [[] for _ in range(n)]
for x in ab:
    a = x[0]
    b = x[1]
    lis[a].append(b)
    lis[b].append(a)
g_n = 0
def dfs(now):
    global g_n
    group[now] = g_n
    global group_len_n
    group_len_n += 1
    for i in lis[now]:
        if group[i] == -1:
            dfs(i)
group_len = []
for i in range(n):
    if group[i] == -1:
        group_len_n = 0
        dfs(i)
        group_len.append(group_len_n)
        g_n += 1
friend = [0 for _ in range(n)]
block = [0 for _ in range(n)]
for x in ab:
    a = x[0]
    b = x[1]
    if group[a] == group[b]:
        friend[a] += 1
        friend[b] += 1
for x in cd:
    c = x[0]
    d = x[1]
    if group[c] == group[d]:
        block[c] += 1
        block[d] += 1
ans = []
for i in range(n):
    ans.append(str(group_len[group[i]] - friend[i] - block[i] -1))
print(" ".join(ans))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納　xが根のとき-(サイズ)を格納
        self.par = [-1 for i in range(n)]
        self.n = n

    def find(self, x):
        #根ならその番号を返す
        if self.par[x] < 0:
            return x
        else:
            #親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_same(self, x, y):
        #根が同じならTrue
        return self.find(x) == self.find(y)

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

        #木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.par[x] > self.par[y]:
            x, y = y, x

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

    def size(self, x):
        return -self.par[self.find(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.par) 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())
graph = [set() for _ in range(N)]
block = [set() for _ in range(N)]
union = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    graph[a-1].add(b-1)
    graph[b-1].add(a-1)
    union.unite(a-1, b-1)
for i in range(K):
    a, b = map(int, input().split())
    block[a-1].add(b-1)
    block[b-1].add(a-1)

blocking = [0] * N
for i, blo in enumerate(block):
    for b in blo:
        if union.is_same(i, b):
            blocking[i] += 1

for i in range(N):
    ans = union.size(i) - len(graph[i]) - blocking[i] - 1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic={}
    while use:
      check=use.popleft()
      if check not in aldic:
        aldic[check]=1
        for x in fr[check-1]:
          use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])

Submission status: Accepted

Solution code:
from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic={}
    while use:
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic[check]=1
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200100)
n, m, k = map( int, input().split() )
friend = [ [] for _ in range( n ) ]

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

graph_id = [ -1 for _ in range( n ) ]

def dfs( ver, g_id ):
    if graph_id[ ver ] == -1:
        graph_id[ ver ] = g_id
    else:
        return
    for next_v in friend[ ver ]:
        dfs( next_v, g_id )

g_id = 0
for ver in range( n ):
    if graph_id[ ver ] != -1:
        continue
    dfs( ver, g_id )
    g_id += 1

graph_size = [ 0 for _ in range( n ) ]
for ver in range( n ):
    graph_size[ graph_id[ ver ] ] += 1

ans = [ graph_size[ graph_id[ ver ] ] for ver in range( n ) ]

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

for ver in range( n ):
    ans[ ver ] = ans[ ver ] - len( friend[ ver ] ) - 1

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