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: Time Limit Exceeded

Solution code:
N,M,K = list(map(int,input().split()))
import sys
input = sys.stdin.readline

from collections import defaultdict
class UF():
  def __init__(self,n):
    self.n_node = n
    self.l = [i for i in range(n)]
    self.size = [1 for i in range(n)]
    self.d = None
    
  def union(self,i,j):
    if not self.connected(i,j):
      root = self.root(i)
      merged_size = self.size[i] + self.size[j] 
      self.size[i] = merged_size
      self.size[j] = merged_size
      for node in self.path(i):
        self.l[node] = root
      for node in self.path(j):
        self.l[node] = root
  
  def path(self,i):
    result = [i]
    while self.l[i] != i:
      i = self.l[i]
      result.append(self.l[i])
    return result
  
  def root(self,i):
    while self.l[i] != i:
      i = self.l[i]
    return i
    
  def connected(self,i,j):
    if self.root(i) == self.root(j):
      return True
    else:
      return False
    
  def size(self,i):
    if self.root(i) == self.root(j):
      return True
    else:
      return False
  
  def simplify(self):
    for node in range(self.n_node):
      root = self.root(self.l[node])
      if self.l[node] != root:
        self.l[node] = root
  
  def calc_connected(self):
    self.d = defaultdict(set)
    self.simplify()
    for idx,root in enumerate(self.l):
      self.d[root] |= {idx}
      
  def connected_set(self,i):
    if self.d is None:
      self.calc_connected()
    return self.d[self.root(i)]
      
uf = UF(N)
direct_connected = defaultdict(set)
for i in range(M):
  i,j = list(map(int,input().split()))
  i-=1
  j-=1
  
  uf.union(i,j)
  direct_connected[i] |= {j}
  direct_connected[j] |= {i}

block_list = defaultdict(set)
for i in range(K):
  i,j = list(map(int,input().split()))
  i-=1
  j-=1
  block_list[i] |={j}
  block_list[j] |={i}
from collections import Counter 

c = Counter(uf.l)
whole = {i for i in range(N)}
for i in range(N):
  c_set = uf.connected_set(i)
  print(len(c_set - direct_connected[i] - block_list[i]-{i}),end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M,K = list(map(int,input().split()))
f = [[] for i in range(N)]
b = [[] for i in range(N)]
for i in range(M):
  R = list(map(int,input().split()))
  f[R[0]-1] = f[R[0]-1] + [R[1]-1]
  f[R[1]-1] = f[R[1]-1] + [R[0]-1]

for i in range(K):
  R = list(map(int,input().split()))
  b[R[0]-1] = b[R[0]-1] + [R[1]-1]
  b[R[1]-1] = b[R[1]-1] + [R[0]-1]

def add_link(ANS):
  for p in range(N):
    t = -1
    while len(ANS[p]) !=t :
      t = len(ANS[p])
      for i in ANS[p]:
          ANS[p] = list(set(ANS[p] + ANS[i]))
  return ANS

ANS = f.copy()
ANS = add_link(ANS)

ans = ''
for p in range(N):
  ANS[p] = [x for x in ANS[p] if x not in f[p]+b[p]+[p]]
  ans += str(len(ANS[p])) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M,K = list(map(int,input().split()))
F = [[0]*N for i in range(N)]
B = [[0]*N for i in range(N)]
for i in range(M):
  R = list(map(int,input().split()))
  F[R[0]-1][R[1]-1] = 1
  F[R[1]-1][R[0]-1] = 1
f = [[0]*N for i in range(N)]
for p in range(N):
  f[p] = [j for j in range(N) if F[p][j] == 1]

for i in range(K):
  R = list(map(int,input().split()))
  B[R[0]-1][R[1]-1] = 1
  B[R[1]-1][R[0]-1] = 1
b = [[0]*N for i in range(N)]
for p in range(N):
  b[p] = [j for j in range(N) if B[p][j] == 1]

def add_link(ANS):
  for p in range(N):
    t = -1
    while len(ANS[p]) !=t :
      t = len(ANS[p])
      for i in ANS[p]:
          ANS[p] = list(set(ANS[p] + ANS[i]))
  return ANS

ANS = f.copy()
ANS = add_link(ANS)

ans = ''
for p in range(N):
  ANS[p] = [x for x in ANS[p] if x not in f[p]+b[p]+[p]]
  ans += str(len(ANS[p])) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

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())
F = UnionFind(N)
B = [set() for _ in range(N)]
FF = [0]*N
for _ in range(M):
    a,b = map(int,input().split())
    F.union(a-1,b-1)
    FF[a-1] += 1
    FF[b-1] += 1
# print(F)
for j in range(K):
    a,b = map(int,input().split())
    B[a-1].add(b-1)
    B[b-1].add(a-1)

Y = []
for i in range(N):
    y = F.size(i) - FF[i] -1
    for b in B[i]:
        if b in F.members(i):
            y += -1
    Y.append(str(y))
print(" ".join(Y))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
	def __init__(self, N):
		self.N = N # データ数
		self.d = [-1]*N # 親の番号，根の場合は，-(集合の要素数)

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

	def union(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 -self.d[self.find(x)]


n,m,k = map(int, input().split())
uf = UnionFind(n)
G_friend = [[] for i in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1, input().split())
    G_friend[a].append(b)
    G_friend[b].append(a)
    uf.union(a,b)

num_block = [0]*n
for i in range(k):
    a,b = map(lambda x: int(x)-1, input().split())
    if uf.same(a,b) and b not in G_friend[a]:
        num_block[a] += 1
        num_block[b] += 1

ans = [0]*n
for i in range(n):
    ans[i] = uf.size(i) - len(G_friend[i]) - 1 - num_block[i]
print(*ans)

Submission status: Time Limit Exceeded

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

# DFSテンプレ、計算量=O(N+M)
# N:頂点の数
# M:辺の数

G = [[] for _ in range(N)]
# graphの入力
for _ in range(M):
    a,b = list(map(int,input().split()))
    G[a-1].append(b-1)
    G[b-1].append(a-1)
# print("G:",G)

KG = [[] for _ in range(N)]
# block graphの入力
for _ in range(K):
    a,b = list(map(int,input().split()))
    KG[a-1].append(b-1)
    KG[b-1].append(a-1)
# print("KG:",KG)

# ここまでエラーなし。
"""
def dfs(G,v):
    # global l
    # nを訪問済みにする
    seen[v] = 1
    # l += 1
    # print(v+1)
    seenV.append(v)
    # vから行ける各頂点next_vについて
    for next_v in G[v]:
        if seen[next_v] == 1:
            continue
        dfs(G,next_v)
"""

def dfs(G,v):
    todo = [v]
    # seen = []
    while todo:
        v = todo.pop(0)
        seen[v] = 1
        seenV.append(v)
        for next_v in G[v]:
            if seen[next_v]==1 or next_v in todo:
                continue
            todo.append(next_v)


# Adj_size = [0]*N
# 全頂点を未訪問に初期化。
Adj = [[] for _ in range(N)]
seen = [0]*N
Y = []
for v in range(N):
    # l = 0
    if seen[v] == 0:
        # 未探索ならdfs発動
        seenV = []
        dfs(G,v)
    
        for sv in seenV:
            Adj[sv] = seenV
    """
        print("dfs done !!!")
    print("v=",v+1,"seen:",seen)
    print("seenV:",seenV)
    print("Adj[",v,"] :",Adj[v])
    """
    
    # 出力
    # y = Adj_size[v] - len(G[v])-1
    y = len(Adj[v]) - len(G[v]) - 1
    for k in KG[v]:
        if k in Adj[v]:
            y += -1
    # print("v=",v+1,"y=",y)
    Y.append(str(y))
    # print("")

# print("ADj",Adj)
# print("Y",Y)
# print("G",G)

print(" ".join(Y))

Submission status: Time Limit Exceeded

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
uf = UnionFind(N)      
excl = [set() for _ in range(N)]

for _ in range(M):
  a,b = list(map(int, input().split()))
  a,b = a-1, b-1
  excl[a].add(b)
  excl[b].add(a)
  uf.union(a,b)
  
for _ in range(K):
  a,b = list(map(int, input().split()))
  a,b = a-1, b-1
  excl[a].add(b)
  excl[b].add(a)

ans = [-1] * N
for i in range(N):
  ans[i] = len(set(uf.members(i)).difference(excl[i])) - 1
  
print(" ".join(list(map(str, ans))))
#print(uf)
#print(excl)

Submission status: Time Limit Exceeded

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def int_(num_str):
    return int(num_str) - 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
ans = [0] * N
some = [1] * N
friend = [[False]*N for _ in range(N)]
for i in range(M):
    a, b = map(int_, input().split())
    uf.union(a, b)
    some[a] += 1
    some[b] += 1
for i in range(K):
    c, d = map(int_, input().split())
    if not uf.same(c, d):
        pass
    else:
        some[c] += 1
        some[d] += 1


ans = [uf.size(i) - some[i] for i in range(N)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

def int_(num_str):
    return int(num_str) - 1


N, M, K = map(int, input().split())
uf = UnionFind(N)
ans = [0] * N
some = [1] * N
friend = [[False]*N for _ in range(N)]
for i in range(M):
    a, b = map(int_, input().split())
    uf.union(a, b)
    some[a] += 1
    some[b] += 1
    friend[a][b] = True
    friend[b][a] = True
for i in range(K):
    c, d = map(int_, input().split())
    if not uf.same(c, d):
        pass
    else:
        some[c] += 1
        some[d] += 1


ans = [uf.size(i) - some[i] for i in range(N)]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, N):
        self.roots = list(range(N + 1))
        self.counter = [1] * (N + 1)

    def get_root(self, n):
        if self.roots[n] != n:
            self.roots[n] = self.get_root(self.roots[n])
        return self.roots[n]

    def union(self, a, b):
        a, b = sorted([self.get_root(a), self.get_root(b)])
        if a != b:
            self.roots[b] = a
            self.counter[a] += self.counter[b]
            self.counter[b] = 0

    def find(self, a, b):
        return self.get_root(a) == self.get_root(b)

    def count(self, x):
        return (self.counter[self.get_root(x)])

def resolve():
    N, M, K = [int(x) for x in input().split()]
    list = [[] for _ in range(N)]
    block = [[] for _ in range(N)]

    uf = UnionFind(N)

    for _ in range(M):
        A, B = [int(x)-1 for x in input().split()]
        list[A].append(B)
        list[B].append(A)
        uf.union(A,B)

    for _ in range(K):
        C, D = [int(x)-1 for x in input().split()]
        block[C].append(D)
        block[D].append(C)

    for i in range(N):
        ans = uf.count(i) - len(list[i]) - 1
        for j in block[i]:
            if uf.find(i ,j):
                ans -= 1

        print(ans, end=" ")
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest


class UnionFind:
    def __init__(self, N):
        self.roots = list(range(N + 1))
        self.counter = [1] * (N + 1)

    def get_root(self, n):
        if self.roots[n] != n:
            self.roots[n] = self.get_root(self.roots[n])
        return self.roots[n]

    def union(self, a, b):
        a, b = sorted([self.get_root(a), self.get_root(b)])
        if a != b:
            self.roots[b] = a
            self.counter[a] += self.counter[b]
            self.counter[b] = 0

    def find(self, a, b):
        return self.get_root(a) == self.get_root(b)

    def count(self, x):
        return (self.counter[self.get_root(x)])

def resolve():
    N, M, K = [int(x) for x in input().split()]
    list = [[] for _ in range(N)]
    block = [[] for _ in range(N)]

    uf = UnionFind(N)

    for _ in range(M):
        A, B = [int(x)-1 for x in input().split()]
        list[A].append(B)
        list[B].append(A)
        uf.union(A,B)

    for _ in range(K):
        C, D = [int(x)-1 for x in input().split()]
        block[C].append(D)
        block[D].append(C)

    for i in range(N):
        ans = uf.count(i) - len(list[i]) - 1
        for j in block[i]:
            if uf.find(i ,j):
                ans -= 1

        print(ans, end=" ")
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    N, M, K = [int(x) for x in input().split()]
    global list, block, seen, osusume
    list = [[] for _ in range(N)]
    block = [[] for _ in range(N)]
    seen = [[False] * N for _ in range(N)]
    osusume = [[] for _ in range(N)]

    for _ in range(M):
        A, B = [int(x)-1 for x in input().split()]
        list[A].append(B)
        list[B].append(A)

    for _ in range(K):
        C, D = [int(x)-1 for x in input().split()]
        block[C].append(D)
        block[D].append(C)

    for i in range(N):
        dfs(i, i)
        print(len(osusume[i]), end=" ")

def dfs(v, origin):
    stacka = list[v]
    seen[origin][v] = True

    if not v in list[origin] and not v in block[origin] and v != origin:
        osusume[origin].append(v)

    for i in stacka:
        if(seen[origin][i] == False):
            dfs(i, origin)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

def resolve():
    N, M, K = [int(x) for x in input().split()]
    global list, block, seen, osusume
    list = [[] for _ in range(N)]
    block = [[] for _ in range(N)]
    seen = [[False] * N for _ in range(N)]
    osusume = [[] for _ in range(N)]

    for _ in range(M):
        A, B = [int(x)-1 for x in input().split()]
        list[A].append(B)
        list[B].append(A)

    for _ in range(K):
        C, D = [int(x)-1 for x in input().split()]
        block[C].append(D)
        block[D].append(C)

    for i in range(N):
        dfs(i, i)
        print(len(osusume[i]), end=" ")

def dfs(v, origin):

    stacka = list[v]

    if(seen[origin][v] == True):
        return
    seen[origin][v] = True

    if not v in list[origin] and not v in block[origin] and v != origin:
        osusume[origin].append(v)

    for i in stacka:
        dfs(i, origin)
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def fr_fr():
    pos = deque.popleft()
    if flag[pos] != 1:
        #探索済みでない
        flag[pos] = 1
        deque.extendleft(fr_l[pos])
        if pos not in fr_l[i] and pos not in br_l[i] and pos != i:
            fr2_l[i] += 1

n,m,k=map(int,input().split())
fr_l = [[] for _ in range(n)]
fr2_l = [0]*n
br_l = [[] for _ in range(n)]
l = [0]*n

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

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

deque = deque()

for i in range(n):
    deque.append(i)
    flag = l.copy()

    while len(deque) > 0:
        fr_fr()

for i in fr2_l:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k=map(int,input().split())
fr_l = [[] for _ in range(n)]
fr2_l = [0]*n
br_l = [[] for _ in range(n)]
l = [0]*n

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

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

deque = deque()

for i in range(n):
    deque.append(i)
    flag = l.copy()

    while len(deque) > 0:
        pos = deque.popleft()
        if flag[pos] != 1:
            #探索済みでない
            flag[pos] = 1
            deque.extendleft(fr_l[pos])
            if pos not in fr_l[i] and pos not in br_l[i] and pos != i:
                fr2_l[i] += 1

for i in fr2_l:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

t = time.time()
class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def root(self):
        if self.master:
            return self.master.root
        else:
            return self

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            #print(f"unite {target.rootnum}({target.root.volume}), {self.rootnum}({self.root.volume})")
            if seroot.number < taroot.number:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

nodes = [UnionNode(i) for i in range(N)]

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

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

result = []
for i in range(N):
    rootnode = nodes[i].root
    ret = rootnode.volume - 1
    for out in outlist[i]:
        if nodes[out].root.number == rootnode.number:
            ret -=1
    result.append(ret)

#for i in range(100):
#    print(result[i])

print(" ".join([str(i) for i in result]))

#print(time.time() - t)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def rootnum(self):
        return self.root.number

    @property
    def root(self):
        if self.master:
            return self.master.root
        else:
            return self


    def same(self, target):
        if self.root == target.root:
            return True
        else:
            return False

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            #print(f"unite {target.rootnum}({target.root.volume}), {self.rootnum}({self.root.volume})")
            if seroot.number < taroot.number:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

nodes = [UnionNode(i) for i in range(N)]

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

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

result = []
for i in range(N):
    node = nodes[i]
    ret = node.root.volume - 1
    for out in outlist[i]:
        if nodes[out].rootnum == node.rootnum:
            ret -=1
    result.append(ret)

#for i in range(100):
#    print(result[i])

print(" ".join([str(i) for i in result]))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def friends(friend, array, i, label, t):
    for j in range(len(friend[i])):
        if label[friend[i][j] - 1] == 0:
            label[friend[i][j] - 1] = label[i]
            array.append(friend[i][j] - 1)
            return friends(friend, array, friend[i][j] - 1, label, t + 1)
    
    if t != 1:
        array.pop(-1)
        return friends(friend, array, array[t - 1], label, t - 1)
    else:
        return label   
        
n, m, k = map(int, sys.stdin.readline().split())
a = [0] * m
b = [0] * m
c = [0] * k
d = [0] * k

label = [0] * n
kosu_label = 1

block = [0] * n

ans = [0] * n

for i in range(m):
    a[i], b[i] = map(int, sys.stdin.readline().split())
    
for i in range(k):
    c[i], d[i] = map(int, sys.stdin.readline().split())
    
friend = [[] for i in range(n)]
    
for i in range(m):
    friend[a[i] - 1].append(b[i])
    friend[b[i] - 1].append(a[i])

for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
        label = friends(friend, [-1, i], i, label, 1)
            
    kosu_label = kosu_label + 1

label_s = [0] * kosu_label

for i in range(n):
    label_s[label[i]] = label_s[label[i]] + 1
    
for w in range(k):
    if label[c[w] - 1] == label[d[w] - 1]:
        block[c[w] - 1] = block[c[w] - 1] + 1
        block[d[w] - 1] = block[d[w] - 1] + 1
            
for i in range(n):
    ans[i] = label_s[label[i]] - len(friend[i]) - block[i] - 1
    print(ans[i], end = ' ')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def friends(friend, array, i, label, t):
    for j in range(len(friend[i])):
        if label[friend[i][j] - 1] == 0:
            label[friend[i][j] - 1] = label[i]
            array.append(friend[i][j] - 1)
            return friends(friend, array, friend[i][j] - 1, label, t + 1)
    
    if t != 1:
        array.pop(-1)
        return friends(friend, array, array[t - 1], label, t - 1)
    else:
        return label   
        
n, m, k = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * k
d = [0] * k

label = [0] * n
kosu_label = 1

block = [0] * n

ans = [0] * n

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

for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
        label = friends(friend, [-1, i], i, label, 1)
            
    kosu_label = kosu_label + 1

label_s = [0] * kosu_label

for i in range(n):
    label_s[label[i]] = label_s[label[i]] + 1
    
for w in range(k):
    if label[c[w] - 1] == label[d[w] - 1]:
        block[c[w] - 1] = block[c[w] - 1] + 1
        block[d[w] - 1] = block[d[w] - 1] + 1
            
for i in range(n):
    ans[i] = label_s[label[i]] - len(friend[i]) - block[i] - 1
    print(ans[i], end = ' ')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def friends(friend, array, i, label, t):
    for j in range(len(friend[i])):
        if label[friend[i][j] - 1] == 0:
            label[friend[i][j] - 1] = label[i]
            array.append(friend[i][j] - 1)
            return friends(friend, array, friend[i][j] - 1, label, t + 1)
    
    if t != 1:
        array.pop(-1)
        return friends(friend, array, array[t - 1], label, t - 1)
    else:
        return label   
        
n, m, k = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * k
d = [0] * k

label = [0] * n
kosu_label = 1

block = [0] * n

ans = [0] * n

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

for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
        label = friends(friend, [-1, i], i, label, 1)
            
    kosu_label = kosu_label + 1

label_s = [0] * kosu_label

for i in range(kosu_label):
    label_s[i] = label.count(i)
    
for w in range(k):
    if label[c[w] - 1] == label[d[w] - 1]:
        block[c[w] - 1] = block[c[w] - 1] + 1
        block[d[w] - 1] = block[d[w] - 1] + 1
            
for i in range(n):
    ans[i] = label_s[label[i]] - len(friend[i]) - block[i] - 1
    print(ans[i], end = ' ')

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def friends(friend, array, i, label, t):
    for j in range(len(friend[i])):
        if label[friend[i][j] - 1] == 0:
            label[friend[i][j] - 1] = label[i]
            array.append(friend[i][j] - 1)
            return friends(friend, array, friend[i][j] - 1, label, t + 1)
    
    if t != 1:
        array.pop(-1)
        return friends(friend, array, array[t - 1], label, t - 1)
    else:
        return label   
        
n, m, k = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * k
d = [0] * k

label = [0] * n
kosu_label = 1

block = [0] * n

ans = [0] * n

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

for i in range(n):
    if label[i] == 0:
        label[i] = kosu_label
        label = friends(friend, [-1, i], i, label, 1)
            
    kosu_label = kosu_label + 1

label_s = [0] * kosu_label

for i in range(n):
    label_s[label[i]] = label_s[label[i]] + 1
    
for w in range(k):
    if label[c[w] - 1] == label[d[w] - 1]:
        block[c[w] - 1] = block[c[w] - 1] + 1
        block[d[w] - 1] = block[d[w] - 1] + 1
            
for i in range(n):
    ans[i] = label_s[label[i]] - len(friend[i]) - block[i] - 1

for i in range(n):
    print(ans[i], end = ' ')