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 sys import stdin
nii=lambda: map(int, stdin.readline().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=map(int,input().split())

tree_f=[[] for i in range(n+1)]
tree_g=[[] for i in range(n+1)]

uf=UnionFind(n+1)

for i in range(m):
  a,b=nii()
  tree_f[a].append(b)
  tree_f[b].append(a)
  uf.union(a,b)

#print(len(uf.members(3)))

for i in range(k):
  a,b=nii()
  tree_g[a].append(b)
  tree_g[b].append(a)

for i in range(n):
  i+=1
  sst=list(set(tree_f[i]+tree_g[i]) & set(uf.members(i)))
  cnt=len(sst)
  print(len(uf.members(i))-1-cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():

    from collections import deque
    import sys
    input = sys.stdin.readline

    N,M,K = map(int, input().split())
    ans = [0]*N
    table = [[] for i in range(N)]
    visited = [0]*N
    block = [[] for i in range(N)]
    groups = [[] for i in range(N)]
    for i in range(M):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        table[a].append(b)
        table[b].append(a)
    for i in range(K):
        c,d = map(int, input().split())
        c -= 1
        d -= 1
        block[c].append(d)
        block[d].append(c)



    for i in range(N):
        if visited[i] == 0:
            Q = deque()
            Q.append(i)
            visited[i] = 1
            group = deque()
            group.append(i)
            n = 1
            while Q:
                x = Q.popleft()
                for y in table[x]:
                    if visited[y] == 0:
                        Q.append(y)
                        visited[y] = 1
                        n += 1
                        group.append(y)
            for x in group:
                groups[x] = set(group)
                ans[x] += n-len(table[x])-1

    for i in range(N):
        temp = set(block[i]) & groups[i]
        ans[i] -= len(temp)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
graph_data=[[0]*N for _ in range(N)]
block_data=[[0]*N for _ in range(N)]
edge_set=set()
block_set=set()
for i in range(N):
    graph_data[i][i]=1
for _ in range(M):
    i,j=map(int,input().split())
    edge_set.add((i,j))
    graph_data[i-1][j-1]=graph_data[j-1][i-1]=1
for _ in range(K):
    i,j=map(int,input().split())
    block_set.add((i,j))
    block_data[i-1][j-1]=block_data[j-1][i-1]=1

from collections import deque

def bfs(start, W):
    work_queue = deque([])
    visited = set()
    work_queue.append(start)
    visited.add(start)
    while work_queue:
        here = work_queue.popleft()
        for i, node in enumerate(W[here]):
            if node ==0: continue
            if i not in visited:
                work_queue.append(i)
                visited.add(i)

    return visited

ans=[0]*N
for i in range(N):
    for j in bfs(i,graph_data):
        if graph_data[i][j]==0:
            ans[i]+=1
        if block_data[i][j]==1:
            ans[i]-=1
pri=''
for i in range(N):
    pri+=str(ans[i])
    if i!=N-1:
        pri+=' '
print(pri)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

#friends=[deque([]) for i in range(n)]
groups=[]
#print(tomo,block)

for i in range(m):
    a=tomo[i][0]
    b=tomo[i][1]
    a_ki=-1
    b_ki=-1
    gl=len(groups)
    for i in range(gl):
        if(a in groups[i]):
            a_ki=i
        if(b in groups[i]):
            b_ki=i
    if(a_ki==-1 and b_ki==-1):
        groups.append([a,b])
    elif(a_ki==-1 and b_ki!=-1):
        groups[b_ki].append(a)
    elif(a_ki!=-1 and b_ki==-1):
        groups[a_ki].append(b)
    elif(a_ki != b_ki):
        groups[a_ki]+=groups[b_ki]
        del groups[b_ki]

gl=len(groups)
ans=[0]*n
for i in range(n):
    koho=[]
    for g in groups:
        if(i in g):
            koho=g
    for k in koho:
        if(i==k):
            continue
        if([i,k] in tomo or [k,i] in tomo or [i,k] in block or [k,i] in block ):
            continue
        ans[i]+=1

kotae=""

for i in range(n):
    kotae+=str(ans[i])+" "
print(kotae)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return
            # 違う木に属していた場合rnkを見てくっつける方を決める
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

    def roots(self):
        return [i for i, x in enumerate(self.root) 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)
directcount = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    directcount[a] += 1
    directcount[b] += 1
    uf.Unite(a, b)


res = [0] * n
ures = uf.all_group_members()

for ke in ures:
    cnt = len(ures[ke]) - 1
    for node in ures[ke]:
        res[node] = cnt - directcount[node]

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

#print(directcount)

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

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())
uf = UnionFind(n)

ans=[0  for i in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    uf.union(x-1,y-1)
    ans[x-1]-=1
    ans[y-1]-=1
    
for i in range(k):
    x,y=map(int,input().split())
    if uf.same(x-1,y-1):
        ans[x-1]-=1
        ans[y-1]-=1

for i in range(n):
    ans[i]+=len(uf.members(i))-1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix, lil_matrix

N, M, K = map(int, input().split())
friendly_edges = [tuple(map(int, input().split())) for _ in range(M)]
forbidden_edges = [tuple(map(int, input().split())) for _ in range(K)]

friendly_adjacency = [[0] * N for _ in range(N)]
forbidden_adjacency = [[0] * N for _ in range(N)]

for u, v in friendly_edges:
    friendly_adjacency[u - 1][v - 1] = 1
    friendly_adjacency[v - 1][u - 1] = 1

for u, v in forbidden_edges:
    forbidden_adjacency[u - 1][v - 1] = 1
    forbidden_adjacency[v - 1][u - 1] = 1

fw = floyd_warshall(csr_matrix(friendly_adjacency))
ans = fw - csr_matrix(forbidden_adjacency) * 10 ** 5
for row in ans:
    print(np.count_nonzero(np.where(row == np.inf, -1000, row) > 1), end=" ", flush=True)

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):
    #print(uf.members(i),)
    for j in uf.members(i):
        if j in f[i] or j in b[i] or i==j:
            continue
        ans[i]+=1
print(*ans)

Submission status: Time Limit Exceeded

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

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

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

def find(i):
    while parent[i] != i:
        i = parent[i]
    return i

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



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

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

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



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

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

kouho = [0]*N

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
import numpy as np

n, m, k = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)

es2 = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    es2[c].append(d)
    es2[d].append(c)

ans = [0]*n

for i in range(n):
    visited = [False] * n
    i_good = np.array(es1[i])
    i_bad = np.array(es2[i])
    visited
    queue = deque()
    queue.extend(i_good)

    while len(queue):
        next_ = queue.pop()
        if visited[next_] == False:
            if (not next_ in i_good) and (not next_ in i_bad):
                ans[i] += 1
            visited[next_] = True
            queue.extend(es1[next_])

    ans[i] -= 1
    if ans[i] < 0:
        ans[i] = 0

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x

    
from collections import defaultdict

n, m, k = map(int, input().split())
uf = UnionFindBySize(n+1)
friends = defaultdict(list)
block = defaultdict(list)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
    friends[a].append(b)
    friends[b].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)


parents = uf.parents
members = defaultdict(list)
for i, p in zip(range(1, n+1), uf.parents[1:]):
    members[p].append(i)    

for i in range(1, n+1):
    p = parents[i]
    if parents[p] != p:
        members[p] = list(set(members[parents[p]]) | set(members[p]))
        members[parents[p]] = list(set(members[parents[p]]) | set(members[p]))

ans = []
for i in range(1, n+1):
    F = friends[i]
    p = parents[i]
    M = members[p]
    if parents[p] != p:
         M += members[parents[p]]
    B = block[i]
    ans.append(len(set(M) - set(F) - set(B) - set([i])))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

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

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]

def resolve():
    n,m,k=list(map(int,input().strip().split()))

    uf = UnionFind(n)

    res=[[] for i in range(n)]
    frd=[[] for i in range(n)]
    blk=[[] for i in range(n)]

    for i in range(m):
        a,b=list(map(int,input().strip().split()))
        a-=1
        b-=1
        uf.union(a,b)
        frd[a].append(b)
        frd[b].append(a)
    
    for i in range(k):
        a,b=list(map(int,input().strip().split()))
        a-=1
        b-=1
        #blk[a].append(b)
        #blk[b].append(a)
        frd[a].append(b)
        frd[b].append(a)
    
    rescnt=[]

    for i in range(n):
        ri=0
        for x in uf.members(i):
            if x==i:
                continue
            if x in frd[i]:
                ri+=0
            else:
                ri+=1
        rescnt.append(str(ri))
        ##rescnt.append(str(n-uf.size(i)-len(blk[i])))
    
    print(" ".join(rescnt))

resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

fre = defaultdict(set)
for a, b in AB:
  fre[a - 1].add(b - 1)
  fre[b - 1].add(a - 1)

blo = defaultdict(set)
for c, d in CD:
  blo[c - 1].add(d - 1)
  blo[d - 1].add(c - 1)

#print(fre)
#print(blo)

uf = UnionFind(n)
for a, b in AB:
  uf.union(a-1, b-1)
#print(uf)
print(*[len(set(uf.members(i)) - fre[i] - blo[i]) - 1 for i in range(n)])

Submission status: Time Limit Exceeded

Solution code:
import copy
n, m, k = map(int,input().split())
a = [[] for i in range(n)]
a2 = [i for i in range(n)]
for i in range(m):
  x, y = map(int,input().split())
  a[x-1].append(y-1)
  a[y-1].append(x-1)
  x2 = a2[x-1]
  while x2 != a2[x2]:
    x2 = a2[x2]
  y2 = a2[y-1]
  while y2 != a2[y2]:
    y2 = a2[y2]
  z = min(x2,y2)
  a2[x-1], a2[y-1], a2[x2], a2[y2] = z, z, z, z
a3 = [[] for i in range(n)]
for i in range(n):
  j = a2[i]
  while j != a2[j]:
    j = a2[j]
  a2[i] = j
  a3[j].append(i)
c = [[] for i in range(n)]
for i in range(k):
  x, y = map(int,input().split())
  c[x-1].append(y-1)
  c[y-1].append(x-1)
f = [0]*n
for i in range(n):
  for j in a3[a2[i]]:
    if not(j in a[i]+c[i]+[i]):
      f[j] += 1
print(" ".join([str(i) for i in f]))

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

uf = UnionFind(N)
for a, b in friends:
    uf.union(a-1, b-1)

ans = []
for i in range(N):
    count = 0
    for c in uf.members(i):
        if {i+1, c+1} not in friends and {i+1, c+1} not in blocks and i != c:
            count += 1
    ans.append(count)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K

c= [[float("inf") for _ in range(N)] for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  c[A[i]-1][B[i]-1]=0
  c[B[i]-1][A[i]-1]=0
for k in range(N):
  c[k][k]=0
  
#print(c)

#ワーシャルフロイト法
for k in range(N):
    for i in range(N):
        for j in range(N):
            c[i][j]=min(c[i][j],c[i][k]+c[k][j])
            
for i in range(M):
  c[A[i]-1][B[i]-1]=float("inf")
  c[B[i]-1][A[i]-1]=float("inf")
            
for j in range(K):
  C[j],D[j]= map(int,input().split())
  c[C[j]-1][D[j]-1]=float("inf")
  c[D[j]-1][C[j]-1]=float("inf")

import collections  
for p in range(N):
  d=collections.Counter(c[p])
  print(d[0]-1)

Submission status: Time Limit Exceeded

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

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

for _ in range(m):
  a, b = map(int, input().split())
  friend[a-1].append(b-1)
  friend[b-1].append(a-1)
  
for _ in range(k):
  c, d = map(int, input().split())
  block[c-1].append(d-1)
  block[d-1].append(c-1)
  
groups = []
active = [True] * n
belong = [0] * n
g_index = 0
while any(active):
  idx = active.index(True)
  g = [idx]
  active[idx] = False
  belong[idx] = g_index
  stack = [idx]
  while stack:
    v = stack.pop()
    for i in friend[v]:
      if active[i]:
        stack.append(i)
        active[i] = False
        belong[i] = g_index
        g.append(i)
  groups.append(g)
  g_index += 1
  
for i in range(n):
  size = len(groups[belong[i]]) - 1 - len(friend[i])
  for j in block[i]:
    if j in groups[belong[i]]:
      size -= 1
  print(size, end=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFindByRank():
  def __init__(self, n):
    self.parents = list(range(n))
    self.rank = [0] * n

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

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

    if x == y:
      return

    if self.rank[x] < self.rank[y]:
      self.parents[x] = y
    else:
      self.parents[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1


if __name__ == '__main__':
  N, M, K = list(map(int, input().split()))
  uf = UnionFindByRank(N + 1)
  #A, B, C, D = [0] * M, [0] * M, [0] * K, [0] * K
  friends = set()
  blocks = set()
  for i in range(M):
    # friends
    #A[i], B[i] = list(map(int, input().split()))
    pair = tuple(sorted(map(int, input().split())))
    friends.add(pair)
    uf.union(pair[0], pair[1])
  for i in range(K):
    # blocks
    blocks.add(tuple(sorted(map(int, input().split()))))

res = [0] * N

computed = set()

for i in range(1, N):
  cnt = 0
  for j in range(i + 1, N + 1):
    t = tuple(sorted([i, j]))
    if i != j and not t in blocks and \
            not t in friends and \
            not t in computed and \
            uf.find(i) == uf.find(j):
      cnt += 1
      res[j - 1] += 1
      computed.add(t)
  res[i - 1] += cnt

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

Submission status: Time Limit Exceeded

Solution code:
def warshallFloyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j] = min(edges[i][j], edges[i][k] + edges[k][j])
  return edges

def main():
    n, m, k = map(int, input().split())
    graph = [[float('inf') for _ in range(n)] for _ in range(n)]
    for _ in range(m):
        a, b = (map(int, input().split()))
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = 1
    blocks = [set() for _ in range(n)]
    for _ in range(k):
        c, d = (map(int, input().split()))
        blocks[c-1].add(d-1)
        blocks[d-1].add(c-1)

    cost = warshallFloyd(graph, n)
    ans = [0] * n
    for i in range(n):
        ans[i] = (len([x for x,e in enumerate(cost[i]) if x!=i and e != float('inf') and 2 <= e and x not in blocks[i]]))
    print(' '.join(map(str, ans)))

main()

Submission status: Time Limit Exceeded

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

import collections
import copy


fr = collections.defaultdict(set)
is_same = collections.defaultdict(bool)
for i in range(M):
  a, b = map(int, input().split())
  fr[b].add(a)
  fr[a].add(b)
_fr = copy.deepcopy(fr)

for i in range(1, N + 1):
  prev = set()
  while True:
    next = fr[i] - prev
    prev = copy.copy(fr[i])
    if not next:
      break
    for j in next:
      if i > j or is_same[(i, j)]: continue
      is_same[(i, j)] = True
      fr[i] |= fr[j]
      fr[j] = fr[i]



bl = collections.defaultdict(set)
for i in range(K):
  a, b = map(int, input().split())
  bl[b].add(a)
  bl[a].add(b)

for i in range(1, N + 1):
  bl[i].add(i)

print(
  " ".join(
    str(len(fr[i] - bl[i] - _fr[i]))
    for i in range(1, N + 1)
  )
)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000)

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())
friends=[0]*n
uf = UnionFind(n)
for i in range(m):
    a, b = map(int,input().split())
    uf.union(a-1, b-1)
    friends[a-1]+=1
    friends[b-1]+=1
 
nowlist=list(uf.all_group_members().values())
 
koho=[0]*n
group=[0]*n
number=1
for i in range(n):
    group[i]=uf.find(i)
    koho[i]=uf.size(i)
"""
for nl in nowlist:
    ng=len(nl)
    for nnl in nl:
        koho[nnl]=ng
        group[nnl]=number
    number+=1
 """
for i in range(k):
    c, d = map(int,input().split())
    if group[c-1]==group[d-1]:
        koho[c-1]-=1
        koho[d-1]-=1
 
for i in range(n):
    print(koho[i]-friends[i]-1, end=" ")