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:
from collections import deque
N,M,K = map(int,input().split())
F = {i:set() for i in range(1,N+1)}
B = {i:set() for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    F[a].add(b)
    F[b].add(a)
for _ in range(K):
    c,d = map(int,input().split())
    B[c].add(d)
    B[d].add(c)
A = []
hist = [-1 for _ in range(N+1)]
cnt = -1
for i in range(1,N+1):
    if hist[i]<0:
        cnt += 1
        A1 = set()
        que = deque([i])
        hist[i] = cnt
        A1.add(i)
        while que:
            x = que.popleft()
            for y in F[x]:
                if hist[y]<0:
                    A1.add(y)
                    que.append(y)
                    hist[y]=cnt
        A.append(A1)
C = []
for i in range(1,N+1):
    cnt = hist[i]
    C.append(len(A[cnt]-F[i]-B[i])-1)
print(*C)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import copy 

N ,M ,K = [int(i) for i in input().split(' ')]
AB = defaultdict(deque)

arrive_size = [-1] * N

for _ in range(M):
    a, b = [int(i) for i in input().split(' ')]
    AB[a].append(b)
    AB[b].append(a)

CD = defaultdict(list)
for _ in range(K):
    c, d = [int(i) for i in input().split(' ')]
    CD[c].append(d)
    CD[d].append(c)

def DFS_size(s, Graph):
    stack = deque([s])
    size = 1
    arrive = [0] * N
    tree = set()
    while stack:
        v = stack[-1]
        arrive[v-1] = 1
        tree.add(v)
        if Graph[v]:
            w = Graph[v].popleft()
            if arrive[w-1] == 0:
                if not w in stack:
                    arrive[w-1] =1
                    stack.append(w)
        else:
            stack.pop()

    for i, a in enumerate(arrive):
        if a == 1:
            arrive_size[i] = size

    return tree

tree_all =[]
tree_size = [None] *N
for i in range(1,N+1):
    if arrive_size[i-1] == -1:
        Graph = copy.deepcopy(AB)
        tree = DFS_size(i,Graph)
        for t in tree:
            size = len(tree)
            for block in CD[t]:
                if block in tree:
                    size -= 1
            for friend in AB[t]:
                if friend in tree:
                    size -= 1
            tree_size[t-1] = size - 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def dfs(friends, x):
    visited = [0] * n
    d = deque([x])
    ans = []
    while d:
        num = d.pop()
        
        #print(num, '->',end='')
        
        if visited[num] == 1:
            #print('x')
            continue
        
        visited[num] = 1
        ans.append(num)
        
        for a in friends[num]:
            d.append(a)
        
    #print()
    return ans
        
if __name__ == "__main__":    
    n, m, k = map(int, input().split())
     
    friends = [[] for _ in range(n)]
    for i in range(m):
        x, y = map(lambda z: int(z) - 1, input().split())
        friends[x].append(y)
        friends[y].append(x)
         
    blocks = [[] for _ in range(n)]
    for i in range(k):
        x, y = map(lambda z: int(z) - 1, input().split())
        blocks[x].append(y)
        blocks[y].append(x)
        
    #print(friends)
    #print(blocks)
    
    label = [-1] * n
    vec_len = []
    num = 0
    for i in range(n):
        if label[i] != -1:
            continue
        
        vec = dfs(friends, i)
        vec_len.append(len(vec))
        for j in vec:
            label[j] = num
        
        num += 1
        
    for i in range(n):
        ans = 0
        ans += vec_len[label[i]]
        ans -= len(friends[i])
        
        for b in blocks[i]:
            if label[i] == label[b]:
                ans -= 1
            
        ans -= 1
        
        print(ans, end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def dfs(friends, x):
    visited = [0] * n
    d = deque([x])
    ans = []
    while d:
        num = d.pop()
        
        #print(num, '->',end='')
        
        if visited[num] == 1:
            #print('x')
            continue
        
        visited[num] = 1
        ans.append(num)
        
        for a in friends[num]:
            d.append(a)
        
    #print()
    return ans
        
if __name__ == "__main__":    
    n, m, k = map(int, input().split())
     
    friends = [[] for _ in range(n)]
    for i in range(m):
        x, y = map(lambda z: int(z) - 1, input().split())
        friends[x].append(y)
        friends[y].append(x)
         
    blocks = [[] for _ in range(n)]
    for i in range(k):
        x, y = map(lambda z: int(z) - 1, input().split())
        blocks[x].append(y)
        blocks[y].append(x)
        
    #print(friends)
    #print(blocks)
    
    for i in range(n):
        vec = dfs(friends, i)
        ans = len(vec)
        
        ans -= len(friends[i])
        
        for b in blocks[i]:
            if b in vec:
                ans -= 1
        
        ans -= 1
                
        print(ans, end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
def dfs(friends, x):
    visited = [0] * n
    d = deque([x])
    ans = []
    while d:
        num = d.pop()
        
        #print(num, '->',end='')
        
        if visited[num] == 1:
            #print('x')
            continue
        
        visited[num] = 1
        ans.append(num)
        
        for a in friends[num]:
            d.append(a)
        
    #print()
    return ans
        
if __name__ == "__main__":    
    n, m, k = map(int, input().split())
     
    friends = [[] for _ in range(n)]
    for i in range(m):
        x, y = map(lambda z: int(z) - 1, input().split())
        friends[x].append(y)
        friends[y].append(x)
         
    blocks = [[] for _ in range(n)]
    for i in range(k):
        x, y = map(lambda z: int(z) - 1, input().split())
        blocks[x].append(y)
        blocks[y].append(x)
        
    #print(friends)
    #print(blocks)
    
    for i in range(n):
        vec = dfs(friends, i)
        ans = len(vec)
        
        for f in friends[i]:
            if f in vec:
                ans -= 1
        
        for b in blocks[i]:
            if b in vec:
                ans -= 1
        
        ans -= 1
                
        print(ans, end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input(): return sys.stdin.readline().strip()

DEBUG = False

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

friend_matrix = [[0] * N for _ in range(N)]
block_matrix = [[0] * N for _ in range(N)]

num_frineds = [0] * N

for _ in range(M):
    A, B = map(int, input().split())
    friend_matrix[A-1][B-1] = 1
    friend_matrix[B-1][A-1] = 1
    num_frineds[A-1] += 1
    num_frineds[B-1] += 1

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

if DEBUG:
    # print("friend_matrix: {}".format(friend_matrix))
    print("friend_matrix:")
    for row in friend_matrix:
        print(row)
    # print("block_matrix: {}".format(block_matrix))
    print("block_matrix:")
    for row in block_matrix:
        print(row)
    print("enter!!")

count = 0
labels = [-1] * N
graph_sizes = []
for n in range(N):
    size = 0
    if labels[n-1] == -1:
        queue = deque([n])
        while queue:
            node = queue.popleft()
            if labels[node-1] == -1:
                labels[node-1] = count
                size += 1
            for i in range(N):
                if labels[i-1] == -1 and friend_matrix[node-1][i-1] == 1:
                    queue.append(i)
        count += 1
        graph_sizes.append(size)

if DEBUG:
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))

frind_candidate = [0] * N
for n in range(N):
    # num_block = sum(block_matrix[n])
    num_block = 0
    for i in range(N):
        if block_matrix[n][i] == 1 and labels[n] == labels[i]:
            num_block += 1
    # num_frined = sum(friend_matrix[n])
    num_frined = num_frineds[n]
    if DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    frind_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1
frind_candidate = list(map(str, frind_candidate))
print(" ".join(frind_candidate))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input(): return sys.stdin.readline().strip()

DEBUG = False

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

friend_matrix = [[0] * N for _ in range(N)]
block_matrix = [[0] * N for _ in range(N)]

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

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

if DEBUG:
    # print("friend_matrix: {}".format(friend_matrix))
    print("friend_matrix:")
    for row in friend_matrix:
        print(row)
    # print("block_matrix: {}".format(block_matrix))
    print("block_matrix:")
    for row in block_matrix:
        print(row)
    print("enter!!")

count = 0
labels = [-1] * N
graph_sizes = []
for n in range(N):
    size = 0
    if labels[n-1] == -1:
        queue = deque([n])
        while queue:
            node = queue.popleft()
            if labels[node-1] == -1:
                labels[node-1] = count
                size += 1
            for i in range(N):
                if labels[i-1] == -1 and friend_matrix[node-1][i-1] == 1:
                    queue.append(i)
        count += 1
        graph_sizes.append(size)

if DEBUG:
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))

frind_candidate = [0] * N
for n in range(N):
    # num_block = sum(block_matrix[n])
    num_block = 0
    for i in range(N):
        if block_matrix[n][i] == 1 and labels[n] == labels[i]:
            num_block += 1
    num_frined = sum(friend_matrix[n])
    if DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    frind_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1
frind_candidate = list(map(str, frind_candidate))
print(" ".join(frind_candidate))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

DEBUG = False

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

friend_matrix = [[0] * N for _ in range(N)]
block_matrix = [[0] * N for _ in range(N)]

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

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

if DEBUG:
    # print("friend_matrix: {}".format(friend_matrix))
    print("friend_matrix:")
    for row in friend_matrix:
        print(row)
    # print("block_matrix: {}".format(block_matrix))
    print("block_matrix:")
    for row in block_matrix:
        print(row)
    print("enter!!")

count = 0
labels = [-1] * N
graph_sizes = []
for n in range(N):
    size = 0
    if labels[n-1] == -1:
        queue = deque([n])
        while queue:
            node = queue.popleft()
            if labels[node-1] == -1:
                labels[node-1] = count
                size += 1
            for i in range(N):
                if labels[i-1] == -1 and friend_matrix[node-1][i-1] == 1:
                    queue.append(i)
        count += 1
        graph_sizes.append(size)

if DEBUG:
    print("labels: {}".format(labels))
    print("graph_sizes: {}".format(graph_sizes))

frind_candidate = [0] * N
for n in range(N):
    # num_block = sum(block_matrix[n])
    num_block = 0
    for i in range(N):
        if block_matrix[n][i] == 1 and labels[n] == labels[i]:
            num_block += 1
    num_frined = sum(friend_matrix[n])
    if DEBUG:
        print("node: {}, num_frined: {}, num_block: {}".format(n+1, num_frined, num_block))
    frind_candidate[n] = graph_sizes[labels[n]] - num_frined - num_block - 1
frind_candidate = list(map(str, frind_candidate))
print(" ".join(frind_candidate))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    while d:
        temp = d.popleft()
        trace.add(temp)
        searched[temp] = 1
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
    chain = len(trace)
    for j in trace:
        ans[j] = chain - 1 - len(trace&friends[j]) - len(trace&blocks[j])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
links = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    while d:
        temp = d.popleft()
        trace.add(temp)
        searched[temp] = 1
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
    for j in trace:
        ans[j] = len(trace) - 1 - len(trace&friends[j]) - len(trace&blocks[j])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M,K = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
links = [set() for _ in range(N)]
searched = [0] * N
ans = [0] * N
d = deque()
for x, y in AB:
    friends[x-1].add(y-1)
    friends[y-1].add(x-1)
for x, y in CD:
    blocks[x-1].add(y-1)
    blocks[y-1].add(x-1)
for i in range(N):
    if searched[i]:
        continue
    trace = set()
    d.append(i)
    while d:
        temp = d.popleft()
        trace.add(temp)
        searched[temp] = 1
        for x in friends[temp]:
            if searched[x] == 0:
                d.append(x)
    for person in trace:
        links[person] = trace
for i in range(N):
    ans[i] = len(links[i]) - 1 - len(links[i]&friends[i]) - len(links[i]&blocks[i])
print(*ans)

Submission status: Time Limit Exceeded

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

#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.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 False
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if uf.issame(x, y):
  	results[x] += 1
  	results[y] += 1
  
node_members = uf.get_node_members()
#print(node_members, results)

print(" ".join([str(uf.size(i) - results[i] - 1) for i in range(N[0])]))

Submission status: Time Limit Exceeded

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

#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.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 False
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if uf.issame(x, y):
  	results[x] += 1
  	results[y] += 1
  
node_members = uf.get_node_members()
#print(node_members, results)

print(" ".join([str(uf.size(i) - results[i] - 1) for i in range(N[0])]))

Submission status: Time Limit Exceeded

Solution code:
#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.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 False
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [0 for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x] += 1
  results[y] += 1
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  if uf.issame(x, y):
  	results[x] += 1
  	results[y] += 1
  
node_members = uf.get_node_members()
#print(node_members, results)

print(" ".join([str(uf.size(i) - results[i] - 1) for i in range(N[0])]))

Submission status: Time Limit Exceeded

Solution code:
#https://www.slideshare.net/chokudai/union-find-49066733
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * self.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 False
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
        
  def issame(self, x, y):
    return self.find(x) == self.find(y)
  
  def get_node_members(self):
    return [[j for j in range(self.n) if self.issame(i, j)] for i in range(self.n)]
  
  def size(self, x):
    return -self.parents[self.find(x)]
  
N = list(map(int, input().split()))
uf = UnionFind(N[0])
results = [[] for i in range(N[0])]
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x].append(y)
  results[y].append(x)
  uf.union(x, y)
#print(uf.parents)

for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  results[x].append(y)
  results[y].append(x)
  
node_members = uf.get_node_members()
#print(node_members, results)

print(" ".join([str(len(set(node_members[i]) - set(results[i]) - set([i]))) for i in range(N[0])]))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
  def __init__(self, size):
    self.parents = [x for x in range(size)]
    self.sizes = [1] * size
  
  def unite(self, a, b):
    if self.find(a) == self.find(b):
      return
    
    if self.size_of(a) > self.size_of(b):
      self.sizes[self.find(a)] += self.size_of(b)
      self.parents[self.find(b)] = self.find(a)
    else:
      self.sizes[self.find(b)] += self.size_of(a)
      self.parents[self.find(a)] = self.find(b)
  
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.sizes[self.find(a)]
  
  def find(self, a):
    if a == self.parents[a]:
      return a
    else:
      self.parents[a] = self.find(self.parents[a])
      return self.parents[a]


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

u = UnionFind(N)

# 自分自身・友達・ブロック関係のいずれかの場合はフラグ立つ
relations = [1 << i for i in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  relations[a] |= 1 << b
  relations[b] |= 1 << a
  u.unite(a, b)
  
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if u.is_same(c, d):
    relations[c] |= 1 << d
    relations[d] |= 1 << c

candidates = []

for i in range(N):
  # candidates.append(u.size_of(i) - bin(relations[i]).count('1'))
  candidates.append(u.size_of(i) - bin(relations[i]).count('1'))
    
print(' '.join(str(x) for x in candidates))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
  def __init__(self, size):
    self.parents = [x for x in range(size)]
    self.sizes = [1] * size
  
  def unite(self, a, b):
    if self.find(a) == self.find(b):
      return
    
    if self.size_of(a) > self.size_of(b):
      self.sizes[self.find(a)] += self.size_of(b)
      self.parents[self.find(b)] = self.find(a)
    else:
      self.sizes[self.find(b)] += self.size_of(a)
      self.parents[self.find(a)] = self.find(b)
  
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.sizes[self.find(a)]
  
  def find(self, a):
    if a == self.parents[a]:
      return a
    else:
      self.parents[a] = self.find(self.parents[a])
      return self.parents[a]


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

u = UnionFind(N)

# 自分自身・友達・ブロック関係のいずれかの場合はフラグ立つ
relations = [1 << i for i in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  relations[a] |= 1 << b
  relations[b] |= 1 << a
  u.unite(a, b)
  
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if u.is_same(c, d):
    relations[c] |= 1 << d
    relations[d] |= 1 << c

candidates = []

for i in range(N):
  candidates.append(u.size_of(i) - bin(relations[i]).count('1'))
    
print(' '.join(str(x) for x in candidates))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
  def __init__(self, size):
    self.parents = [x for x in range(size)]
    self.sizes = [1] * size
  
  def unite(self, a, b):
    if self.find(a) == self.find(b):
      return
    
    if self.size_of(a) > self.size_of(b):
      self.sizes[self.find(a)] += self.size_of(b)
      self.parents[self.find(b)] = self.find(a)
    else:
      self.sizes[self.find(b)] += self.size_of(a)
      self.parents[self.find(a)] = self.find(b)
  
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.sizes[self.find(a)]
  
  def find(self, a):
    if a == self.parents[a]:
      return a
    else:
      return self.find(self.parents[a])


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

u = UnionFind(N)

# 自分自身・友達・ブロック関係のいずれかの場合はフラグ立つ
relations = [1 << i for i in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  relations[a] |= 1 << b
  relations[b] |= 1 << a
  u.unite(a, b)
  
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if u.is_same(c, d):
    relations[c] |= 1 << d
    relations[d] |= 1 << c

candidates = []

for i in range(N):
  candidates.append(u.size_of(i) - bin(relations[i]).count('1'))
    
print(' '.join(str(x) for x in candidates))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
  def __init__(self, size):
    self.parents = [x for x in range(size)]
    self.sizes = [1] * size
  
  def unite(self, a, b):
    if self.find(a) == self.find(b):
      return
    
    if self.size_of(a) > self.size_of(b):
      self.sizes[self.find(a)] += self.size_of(b)
      self.parents[self.find(b)] = self.find(a)
    else:
      self.sizes[self.find(b)] += self.size_of(a)
      self.parents[self.find(a)] = self.find(b)
  
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.sizes[self.find(a)]
  
  def find(self, a):
    if a == self.parents[a]:
      return a
    else:
      return self.find(self.parents[a])


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

u = UnionFind(N)

friendship = [[False] * (N) for _ in range(N)]
blocking = [[False] * (N) for _ in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  friendship[a][b] = True
  friendship[b][a] = True
  u.unite(a, b)
  
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  blocking[c][d] = True
  blocking[d][c] = True

candidates = []
# 10^10 :cry
for n in range(N):
  candidates.append(sum(
    m != n and not friendship[n][m] and not blocking[n][m] and u.is_same(n, m)
    for m in range(N)
  ))
    
print(' '.join(str(x) for x in candidates))

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



def main():
    n,m,k = map(int,input().split())
    friend = [[] for i in range(n)]
    block = [[] for i in range(n)]

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

    un = UnionFind(n)
    
    for i in range(len(friend)):
        for j in range(len(friend[i])):
            # print(i,friend[i][j])
            un.union(i,friend[i][j])

    # print(un)

    ans = []
    for i in range(n):
        ans.append(str(len((set(un.members(i)) - (set(block[i])|set(friend[i]))))-1))

    print(' '.join(ans))
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
N, M, K = list(map(int, input().split()))
F = [[0 for _ in range(N)] for _ in range(N)]
B = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    F[a][b] = 1
    F[b][a] = 1

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

# まだ探索済みでない頂点からdfs
# どの頂点がどの連結成分に属するかを管理
connect_group = {}

for i in range(N):
    if connect_group.get(i) is not None:
        continue
    stack = deque()
    stack.append(i)
    connect_group[i] = i
    p = -1    
    while len(stack):
        j = stack.pop()
        connect_group[j] = i
        for k, v in enumerate(F[j]):
            if v == 1 and connect_group.get(k) is None:
                stack.append(k)
                connect_group[k] = i
                
ans = []
connect_len = Counter(connect_group.values())
for i in range(N):
    g = connect_group[i]
    l = connect_len[g]
    x = 0
    for j in range(N):
        if i != j:
            if g == connect_group[j]:
                if F[i][j] or B[i][j]:
                    x += 1
    ans.append(str(l - x - 1))

print(' '.join(ans))