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 = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

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_friend = UnionFind(N)
# uf_block = UnionFind(N)

es_friend = [[False for _ in range(N)] for _ in range(N)]
es_block = [[False for _ in range(N)] for _ in range(N)]

for i in range(M):
    uf_friend.union(AB[i][0]-1, AB[i][1]-1)
    es_friend[AB[i][0]-1][AB[i][1]-1] = True
    es_friend[AB[i][1]-1][AB[i][0]-1] = True
for i in range(K):
    # uf_block.union(CD[i][0]-1, CD[i][1]-1)
    es_block[CD[i][0]-1][CD[i][1]-1] = True
    es_block[CD[i][1]-1][CD[i][0]-1] = True

# print(es_friend)
# print(es_block)
# for i in range(N):
#     print(uf_friend.members(i), uf_block.members(i))


ans = [0 for _ in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if (es_friend[i][j] == es_block[i][j] == False) and uf_friend.same(i, j):
            ans[i] += 1
            ans[j] += 1
print(" ".join(list(map(str, ans))))

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friend = [0] * (n+1)
block = [0] * (n+1)

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

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

groups = list(uf.all_group_members().values())
w = [0] * (n+1)

for group in groups:
    r = len(group)
    for member in group:
        member += 1
        w[member] = r - friend[member] - block[member] - 1

print(*w[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M, K = map(int, input().split())

# 人iの友達関係リスト
set_Friend = [set() for i in range(N)]
for j in range(M):
  A, B = map(int, input().split())
  set_Friend[A-1].add(B-1)
  set_Friend[B-1].add(A-1)

# 人iのブロック関係リスト
set_Block = [set() for i in range(N)]
for j in range(K):
  C, D = map(int, input().split())
  set_Block[C-1].add(D-1)
  set_Block[D-1].add(C-1)

# 友達関係による連結成分
cluster_id = 0
clusters = []
clustering = [-1 for i in range(N)]
remaining_user = N
for i in range(N):
  if clustering[i]!=-1:
    continue
  cluster_prev = set([i])
  cluster_diff = set([i])
  while len(cluster_diff)>0:
    cluster_next = set()
    for j in cluster_diff:
      cluster_next = cluster_next | set_Friend[j]
    cluster_diff = cluster_next - cluster_prev
    cluster_prev = cluster_next | cluster_prev
  for k in cluster_prev:
    clustering[k] = cluster_id
  clusters.append(cluster_prev)
  remaining_user -= len(cluster_prev)
  if remaining_user==0:
    break
  cluster_id += 1

# 友達候補の人数を計算して出力
for i in range(N):
  id = clustering[i]
  print(len(clusters[id]-set_Friend[i]-set_Block[i]-set([i])), end='')
  if i<N-1:
    print(' ', end='')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g

@mt
def slv(N, M, K, AB, CD):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    def dfs(u):
        s = [u]
        done = set(s)
        while s:
            u = s.pop()
            for v in g[u]:
                if v not in done:
                    s.append(v)
                    done.add(v)
        return done

    group = dict()
    done = set()
    parent = [-1] * (N+1)
    for i in range(1, N+1):
        j = dfs(i)
        done |= j
        for k in j:
            parent[k] = i
        group[i] = j

    direct = defaultdict(set)
    for a, b in AB:
        direct[a].add(b)
        direct[b].add(a)
    block = defaultdict(set)
    for c, d in CD:
        block[c].add(d)
        block[d].add(c)

    ans = []
    for i in range(1, N+1):
        cand = group[parent[i]] - set([i])
        cand = cand - block[i]
        cand = cand - direct[i]
        ans.append(len(cand))
    return ans


def main():
    N, M, K = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(K)]
    print(*slv(N, M, K, AB, CD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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 solve():
    N, M, K = map(int, input().split())
    friendship = [set() for _ in range(N + 1)]
    uf_tree = UnionFind(N + 1)
    for i in range(M):
        a, b = map(int, input().split())
        friendship[a].add(b)
        friendship[b].add(a)
        if not uf_tree.same(a, b):
            uf_tree.union(a, b)
    block = [set() for _ in range(N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    
    ans = [0] * (N + 1)
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            if j in block[i]:
                continue
            if j in friendship[i]:
                continue
            if uf_tree.same(i, j):
                ans[i] += 1
                ans[j] += 1
    print(' '.join(map(str, ans[1:])))


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:

class UnionFind(object):
    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):
        groups = {}
        for i in xrange(self.n):
            r = self.find(i)
            groups.setdefault(r, set()).add(i)
        return groups.values()


def main():
    n, m, k = map(int, raw_input().split())
    uf = UnionFind(n)
    ff = {i: {i} for i in xrange(n)}
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        ff[a].add(b)
        ff[b].add(a)
        uf.union(a, b)
    for _ in xrange(k):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        ff[a].add(b)
        ff[b].add(a)

    clusters = uf.all_group_members()
    ans = [0] * n
    for cluster in clusters:
        for i in cluster:
            size = len(cluster - ff[i])
            ans[i] = size
    print ' '.join(map(str, ans))

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

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

#%%
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 group_members(self):
        return [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)
for a,b in AB:
    uf.union(a-1,b-1)
    
ans = [0]*N

for group in uf.group_members():
    L = len(group)-1
    for a in group:
        ans[a] = L
        
# friends = [0]*N
# brock = [0]*N
for a,b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c,d in CD:
    if uf.same(c-1,d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m, k = map(int, sys.stdin.readline().split())
ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
cd = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]
friend = [set() for _ in range(n+1)]
for a, b in ab:
    friend[a].add(b)
    friend[b].add(a)
block = [set() for _ in range(n+1)]
for c, d in cd:
    block[c].add(d)
    block[d].add(c)

root = list(range(n+1))
size = [1] * (n + 1)
height = [1] * (n + 1)

def find_root(u):
    v = root[u]
    if v == u:
        return u 
    w = find_root(v)
    root[u] = w 
    return w 

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru != rv:
        if height[ru] >= height[rv]:
            root[rv] = ru 
            height[ru] = max(height[ru], height[rv] + 1)
            size[ru] += size[rv]
        else:
            root[ru] = rv 
            size[rv] += size[ru]

def main():
    for u in range(1, n+1):
        for v in friend[u]:
            unite(u, v)
    
    g = [set() for _ in range(n+1)]
    for i in range(1, n+1):
        find_root(i)
        g[root[i]].add(i)
    
    for i in range(1, n+1):
        yield len(g[root[i]] - friend[i] - block[i]) - 1

if __name__ == '__main__':
    ans = main()
    print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import queue
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(str(b))
    dic[str(b)].append(str(a))
seen = set()
def BFS(dic,node,seen):
    cc = set()
    q = queue.Queue()
    q.put(node)
    seen.add(node)
    while not q.empty():
        now_node = q.get()
        cc.add(now_node)
        target = dic[now_node]
        for tgt in target:
            if tgt not in cc:
                q.put(tgt)
                seen.add(tgt)
    return cc,seen
c_comp=[]
for i in range(1,N+1):
    if str(i) not in seen:
        # 連結判定
        tmp = BFS(dic,str(i),seen)
        seen = tmp[1]
        c_comp.append(tmp[0])

for (a,b) in cd:
    for ls in c_comp:
        #print(ls)
        if str(a) in ls and str(b) in ls:
            dic[str(a)].append(str(b))
            dic[str(b)].append(str(a))
res = [0]*N
for ls in c_comp:
    leng = len(ls)-1
    for idx in ls:
        #print(idx, len(dic[idx]), leng)
        res[int(idx)-1] = leng - len(dic[idx])
print(*res)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, M, K = map(int, input().split())
uf_fr = UnionFind(N)
friends = [set([]) for _ in range(N)]
brocks = [set([]) for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    friends[a] |= {b}
    friends[b] |= {a}
    uf_fr.union(a, b)
for _ in range(K):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    brocks[a] |= {b}
    brocks[b] |= {a}
clusters = {}
for i in range(N):
    clusters.setdefault(uf_fr.find(i), set([]))
    clusters[uf_fr.find(i)] |= {i}
print(*[len(clusters[uf_fr.find(i)] - brocks[i]) - 1 - len(friends[i]) for i in range(N)])

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

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

tk=UnionFind(n)

kk=[[False] * n for _ in range(n)]

for _ in range(m):
    a,b=map(int, input().split())
    kk[a-1][b-1]=True
    kk[b-1][a-1]=True
    tk.union(a-1, b-1)

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

for i in range(n):
    tmp=tk.members(i)
    ans=-1
    for val in tmp:
        if not kk[i][val]:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int, input().split( ))
F = [tuple(map(int, input().split( ))) for _ in range(m)]
B = [tuple(map(int, input().split( ))) for _ in range(k)]
Fx = [0 for i in range(n+1)]
Bx = [0 for i in range(n+1)]
for a,b in F:
    Fx[a]|=(1<<(b-1))
    Fx[b]|=(1<<(a-1))
for a,b in B:
    Bx[a]|=(1<<(b-1))
    Bx[b]|=(1<<(a-1))
#友達関係での連結成分で分解
#連結成分中から2つ選ぶ場合の数から友達関係とブロック関係を引く
#各人ごと
#https://tjkendev.github.io/procon-library/python/union_find/union_find.html
*p, = range(n+1)
rank = [1]*(n+1)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1
for a,b in F:
    unite(a,b)
dic = {}
for i in range(1,n+1):
    if root(i) in dic:
        dic[root(i)] |= 1<<(i-1)
    else:
        dic[root(i)] = 1<<(i-1)
for i in range(1,n+1):
    ans = dic[root(i)]&(-1^ (Fx[i]|Bx[i]))
    print(bin(ans).count("1")-1,end = " ")

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

u = UnionFind(n)

frends = [set() for i in range(n)]

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

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

ans = [0 for i in range(n)]

for y in u.all_group_members().values():
    x = set(y)
    for j in x:
        ans[j] = len(x - frends[j]) - 1


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

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())
    
from collections import defaultdict
n,m,k=map(int,input().split())
tree = UnionFind(n)
friend=defaultdict(set)
block =defaultdict(set)
for _ in range(m):
    a,b=map(int,input().split())
    tree.union(a-1,b-1)
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)
for _ in range(k):
    a,b=map(int,input().split())
    block[a-1].add(b-1)
    block[b-1].add(a-1)
    
ans=[]
for i in range(n):
    #print(set(tree.members(i)),friend[i],block[i])
    g = set(tree.members(i)) - friend[i] - block[i]
    #print(g)
    l = len(g)
    ans.append(l-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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 members2(self, x, ignore_list):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root and i not in ignore_list]

    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, readline().split())
m = map(int,read().split())
fb = list(zip(m,m))

friend = fb[:M]
block = fb[M:]
uf = UnionFind(N)
for a, b in friend:
    uf.union(a-1, b-1)

ignore = [[i] for i in range(N+1)]
for c, d in fb:
  ignore[c-1].append(d-1)
  ignore[d-1].append(c-1)

ans = []
for i in range(N):
    friend_list = uf.members2(i, ignore[i])
    #print(friend_list)
    ans.append(str(len(friend_list)))

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
def inputs(): return (int(x) for x in 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())
N,M,K = inputs()
uf = UnionFind(N+1)
f = {i:[] for i in range(N)}
b = {i:[] for i in range(N)}
ans = [0]*(N)
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    f[x-1].append(y-1)
    f[y-1].append(x-1)
    uf.union(x-1,y-1)
for _ in range(K):
    x,y = inputs()
    b[x-1].append(y-1)
    b[y-1].append(x-1)
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        if not j in f[i] and not j in b[i] and uf.same(i,j):
            ans[i]+=1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[C]>size[B]:
        P[B]=P[C]
    else:
        P[C]=P[B]
G=[0 for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a]+=1
    G[b]+=1
    union(a,b)
#print(P)
PP=[]
for i in range(N+1):
    PP.append(find(P[i]))
#print(PP)
PPP=[0 for i in range(N+1)]
for i in range(1,N+1):
    PPP[PP[i]]+=1
#print(PPP)

B=[[]for i in range(N+1)]
for i in range(K):
    c,d=map(int,input().split())
    B[c].append(d)
    B[d].append(c)
#print(G)
#print(B)
ans=[]
for i in range(1,N+1):
    ANS=PPP[PP[i]]-1-G[i]
    for j in B[i]:
        if find(j)==PP[i]:
            ANS-=1
    ans.append(ANS)
print(*ans)