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:
class UF:
    #経路圧縮のみのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している

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

    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)
        if a_par == b_par:
            return
        else:
            self.parents[a_par] += self.parents[b_par]
            self.parents[b_par] = a_par

    def length(self,n):
        par = self.find(n)
        return abs(self.parents[par])

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



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [[] for _ in range(n+1)]
    friend_lst = [[] for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        if b not in friend_lst[a]:friend_lst[a].append(b)
        if a not in friend_lst[b]:friend_lst[b].append(a)
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if d not in block_lst[c]:block_lst[c].append(d)
        if c not in block_lst[d]:block_lst[d].append(c)
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        #print(i,"の最初の友達候補の数は",uf.length(i)-1)
        f_o_f = uf.length(i) - 1
        #print(i,"の友達リスト",friend_lst[i])
        f_o_f -= len(friend_lst[i])
        #print(i,"のブロックした相手は",block_lst[i])
        f_o_f -= len([b for b in block_lst[i] if uf.is_same(i,b) and b not in friend_lst[i]])
        answer.append(f_o_f)

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






if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df.get(a).add(b)
        Df.get(b).add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db.get(c).add(d)
        Db.get(d).add(c)

    Q = deque()
    C = {}
    ANS = {}
    for i in range(1, n + 1):
        if C.get(i):
            continue

        C[i] = True
        Cin = {}
        Cin[i] = True
        Q.appendleft(i)
        while len(Q) != 0:
            for f in Df.get(Q.pop()):
                if not Cin.get(f):
                    Q.appendleft(f)
                    C[f] = True
                    Cin[f] = True

        for k in Cin.keys():
            ANS[k] = len(Cin) - len(Df[k]) - len(Cin.keys() & Db[k] - Df[k]) - 1

    print(*[ANS[i] for i in range(1, n + 1)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df[a].add(b)
        Df[b].add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db[c].add(d)
        Db[d].add(c)

    Q = []
    C = {}
    ANS = {}
    for i in range(1, n + 1):
        if C.get(i):
            continue

        C[i] = True
        Cin = {}
        Cin[i] = True
        Q.append(i)
        while len(Q) != 0:
            for f in Df[Q.pop(0)]:
                if not Cin.get(f):
                    Q.append(f)
                    C[f] = True
                    Cin[f] = True

        for k in Cin.keys():
            ANS[k] = len(Cin) - len(Df[k]) - len(Cin.keys() & Db[k] - Df[k]) - 1

    print(*[ANS[i] for i in range(1, n + 1)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
c=[list(map(int,input().split())) for i in range(k)]

lf=[[] for i in range(n)]
for i in range(m):
    lf[a[i][0]-1].append(a[i][1])
    lf[a[i][1]-1].append(a[i][0])
lb=[[] for i in range(n)]
for i in range(k):
    lb[c[i][0]-1].append(c[i][1])
    lb[c[i][1]-1].append(c[i][0])

lc=[[] for i in range(n)]
for i in range(m):
    lc[a[i][0]-1].append(a[i][1])
    lc[a[i][1]-1].append(a[i][0])

ll=[]
for i in range(n):
    if i not in ll:
        l=set(lc[i])
        for j in lc[i]:
            for p in lf[j-1]:
                if p not in l:
                    lc[i].append(p)
                    l.add(p)
        for j in l:
            lc[j-1]=lc[i]
            ll.append(j-1)

lm=[]
for i in range(n):
    lm.append(len(lc[i])-len(lf[i])-1)
    for j in lb[i]:
        if j in lc[i]:
            lm[i]-=1

for i in lm:
    if i<0:
        print(0,end=" ")
    else:
        print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df[a].add(b)
        Df[b].add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db[c].add(d)
        Db[d].add(c)

    Q = []
    ANS = {}
    C = [False] * (n + 1)
    for i in range(1, n + 1):
        if C[i]:
            continue

        C[i] = True
        Cin = [False] * (n + 1)
        Cin[i] = True
        FF = set()
        FF.add(i)
        Q.append(i)
        while len(Q) != 0:
            for f in Df[Q.pop(0)]:
                if not Cin[f]:
                    Q.append(f)
                    FF.add(f)
                    C[f] = True
                    Cin[f] = True

        for ni in range(1, n + 1):
            if Cin[ni]:
                ANS[ni] = (Cin.count(True) - len(Df[ni]) - len(FF & Db[ni] - Df[ni]) - 1)

    print(*[ANS[i] for i in range(1, n + 1)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

friend=[[] for _ in range(n)]
for ab in friends_pair:
    a,b = ab
    friend[a].append(b)
    friend[b].append(a) 
    
block=[]
for i in range(k):
    a,b = map(int,input().split())
    block.append((a-1,b-1))

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0
while sum(visited)<n:
    for i in range(n):
        if visited[i]==0:
            start=i
            break
    
    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
        for y in friend[x]:
            if y == parent:#親ノードを飛ばし
                continue
            if visited[y]==0:
                q.append((x,y))#子ノードを追加
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c
#        print(parent,x,q)
    clusters.append(cluster)
    i_c+=1
#ans=[]
# for i in range(n):
#     friend_cand = [j for j in range(n) if j in clusters[list_cluster[i]] ]
#     #print(friend_cand)
#     ans.append( len([ff for ff in friend_cand if ff not in block[i] and ff not in friend[i] ] ) -1)

# same_cluster = [clusters[list_cluster[i]] for i in range(n) ]
# for i in range(n):
#     same = same_cluster[i]
#     ans.append(  len([s for s in same_cluster[i] if s!=i and s not in friend[i] and s not in block[i]]) )

#print(*ans)

ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
for f in friends_pair:
    if list_cluster[f[0]] ==  list_cluster[f[1]]:
        ans[f[0]]-=1
        ans[f[1]]-=1
for b in block:
    if list_cluster[b[0]] ==  list_cluster[b[1]]:
        ans[b[0]]-=1
        ans[b[1]]-=1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df[a].add(b)
        Df[b].add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db[c].add(d)
        Db[d].add(c)

    Q = []
    ANS = []
    for i in range(1, n + 1):
        cnt = 0
        FF = set()
        C = [False]*(n + 1)
        C[i] = True
        Q.append(i)
        while len(Q) != 0:
            for f in Df[Q.pop(0)]:
                if not C[f]:
                    Q.append(f)
                    FF.add(f)
                    C[f] = True
                    cnt += 1

        ANS.append(cnt - len(Df[i]) - len(FF & Db[i] - Df[i]))

    print(*ANS)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)


D = {}
parent = [-1] * N
visited = [False] * N
for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    stack = [root]
    while stack:
        n = stack.pop()
        visited[n] = True
        parent[n] = root

        for to in F[n]:
            if visited[to]:
                continue
            D[root].add(to)
            stack.append(to)

ans = [0] * N
for iam in range(N):
    group = D[parent[iam]]
    tmp_ans = len(group) - len(F[iam]) - 1
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, k = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(m)]
    CD = [[int(e) for e in input().split()] for i in range(k)]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for ab in AB:
        Df[ab[0]].add(ab[1])
        Df[ab[1]].add(ab[0])

    for cd in CD:
        Db[cd[0]].add(cd[1])
        Db[cd[1]].add(cd[0])

    Q = []
    ANS = []
    for i in range(1, n + 1):
        FF = set()
        C = [False]*(n + 1)
        C[i] = True
        Q.append(i)
        while len(Q) != 0:
            for f in Df[Q.pop(0)]:
                if not C[f]:
                    Q.append(f)
                    FF.add(f)
                    C[f] = True

        ANS.append(C.count(True) - len(Df[i]) - len(FF & Db[i] - Df[i]) - 1)

    print(*ANS)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#visited を 0-1の辞書にする
def DFS(s,visited,graph,ret):
    #今いる場所をvisitedに
    visited[s] = 1
    ret.append(s)
    #これから探索するところを一時的にしまっておく場所
    queue = []
    #幅優先探索なので、あるエッジとつながっているところを全て
    for i in range(len(graph[s])):
        #俺たちはもう、辿り着いてた...
        if visited[graph[s][i]]:
            continue
        queue.append(graph[s][i])
    for i in range(len(queue)):
        if visited[queue[i]]:
            continue
        DFS(queue[i],visited,graph,ret)
    return ret

[n,m,k] = [int(i) for i in input().split()]
dic_b = {}
dic_f = {}
for i in range(n):
    dic_f[i] = []
    dic_b[i] = []

table_f = [[0] * n for i in range(n)]
table_b = [[0] * n for i in range(n)]

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


for i in range(k):
    [c,d] = [int(i)-1 for i in input().split()]
    dic_b[c].append(d)
    dic_b[d].append(c)
    table_f[c][d] = 1
    table_f[d][c] = 1

vis_dic = {}

for i in range(n):
    vis_dic[i] = 0

tmp = vis_dic.copy()

for i in range(n):
    ans = -1
    vis_dic = tmp.copy()

    cands = DFS(i,vis_dic,dic_f,[])
    #print(cands, end = " ")
    for cand in cands:
        if table_f[i][cand] == 1 or table_b[i][cand] == 1:
            ans -= 1
    if i != n-1:
        print(max(0,ans+len(cands)),end = " ")
    else:
        print(max(0,ans+len(cands)))
    #print("")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from collections import Counter

N, M, K = list(map(int, input().split()))
G = [[] for _ in range(N)]
deg = [0 for _ in range(N)]
reds = [[] for _ in range(N)]

for _ in range(M):
    _a, _b = list(map(int, input().split()))
    _a -= 1
    _b -= 1
    G[_a].append(_b)
    G[_b].append(_a)
    deg[_a] += 1
    deg[_b] += 1

for _ in range(K):
    _c, _d = list(map(int, input().split()))
    _c -= 1
    _d -= 1
    reds[_c].append(_d)
    reds[_d].append(_c)


# compute connected components
numbers = {i: None for i in range(N)}

def dfs():
    visited = [False for _ in range(N)]
    stack = []
    for i in range(N):
        if not visited[i]:
            stack.append(i)
            while len(stack) > 0:
                v = stack.pop()
                visited[v] = True
                numbers[v] = i
                for neighbor in G[v]:
                    if not visited[neighbor]:
                        stack.append(neighbor)
dfs()

counter = {}
groups = {}
for i in range(N):
    if numbers[i] not in counter:
        counter[numbers[i]] = 1
        groups[numbers[i]] = set({i})
    else:
        counter[numbers[i]] += 1
        groups[numbers[i]].add(i)


for i in range(N):
    v = counter[numbers[i]] - 1
    for c in groups[numbers[i]]:
        if c in G[i] or c in reds[i]:
            v -= 1
    print(v, end='')
    if i < N - 1:
        print(" ", end='')
print()

Submission status: Time Limit Exceeded

Solution code:
#d

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

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

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

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

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0
while sum(visited)<n:
    
    for i in range(n):
        if visited[i]==0:
            start=i
            break
    
    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
    
        for y in friend[x]:
            if y == parent:#親ノードを飛ばし
                continue
            if visited[y]==0:
                q.append((x,y))#子ノードを追加
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c
#        print(parent,x,q)
    clusters.append(cluster)
    i_c+=1

ans=[]
# for i in range(n):
#     friend_cand = [j for j in range(n) if j in clusters[list_cluster[i]] ]
#     #print(friend_cand)
#     ans.append( len([ff for ff in friend_cand if ff not in block[i] and ff not in friend[i] ] ) -1)

same_cluster = [clusters[list_cluster[i]] for i in range(n) ]
for i in range(n):
    same = same_cluster[i]
    ans.append(  len([s for s in same_cluster[i] if s!=i and s not in friend[i] and s not in block[i]]) )

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def DFS(s,visited,graph):
    #今いる場所をvisitedに
    visited.append(s)
    #これから探索するところを一時的にしまっておく場所
    queue = []
    #幅優先探索なので、あるエッジとつながっているところを全て
    for i in range(len(graph[s])):
        #俺たちはもう、辿り着いてた...
        if graph[s][i] in visited:
            continue
        queue.append(graph[s][i])
    for i in range(len(queue)):
        if queue[i] in visited:
            continue
        DFS(queue[i],visited,graph)
    return visited

[n,m,k] = [int(i) for i in input().split()]
dic_b = {}
dic_f = {}
for i in range(n):
    dic_f[i] = []
    dic_b[i] = []

table_f = [[0] * n for i in range(n)]
table_b = [[0] * n for i in range(n)]

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


for i in range(k):
    [c,d] = [int(i)-1 for i in input().split()]
    dic_b[c].append(d)
    dic_b[d].append(c)
    table_f[c][d] = 1
    table_f[d][c] = 1


for i in range(n):
    ans = -1
    ls = []
    cands = DFS(i,ls,dic_f)
    #print(cands, end = " ")
    for cand in cands:
        if table_f[i][cand] == 1 or table_b[i][cand] == 1:
            ans -= 1
    if i != n-1:
        print(max(0,ans+len(cands)),end = " ")
    else:
        print(max(0,ans+len(cands)))
    #print("")

Submission status: Time Limit Exceeded

Solution code:
#d

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

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

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

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

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0
while sum(visited)<n:
    
    for i in range(n):
        if visited[i]==0:
            start=i
            break
    
    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
    visited[start]=1
    list_cluster[start]=i_c
    for togo in friend[start]:
        visited[togo]=1
        cluster.append(togo)
        list_cluster[togo]=i_c
    while q:
        parent,x = q.popleft()
    
        for y in friend[x]:
            if y == parent:#親ノードを飛ばし
                continue
            if visited[y]==0:
                q.append((x,y))#子ノードを追加
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c
#        print(parent,x,q)
    clusters.append(cluster)
    i_c+=1

ans=[]
for i in range(n):
    friend_cand = [j for j in range(n) if j in clusters[list_cluster[i]] ]
    #print(friend_cand)
    ans.append( len([ff for ff in friend_cand if ff not in block[i] and ff not in friend[i] ] ) -1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

line = input().split()
nPerson = int(line[0])
nFriend = int(line[1])
nBlock  = int(line[2])

friends = [[] for i in range(nFriend)]
for i in range(nFriend):
  line = input().split()
  friends[i] =[int(line[0]), int(line[1]) ]

blocks = [[] for i in range(nBlock)]
for i in range(nBlock):
  line = input().split()
  blocks[i] = [int(line[0]), int(line[1]) ]
  
connected = [[] for i in range(nPerson+1)]
  
for i in friends:
  if i[1] not in connected[i[0]]:
    connected[i[0]].append(i[1])
  if i[0] not in connected[i[1]]:
    connected[i[1]].append(i[0])

blocked = [[] for i in range(nPerson+1)]
for i in blocks:
  if i[1] not in blocked[i[0]]:
    blocked[i[0]].append(i[1])
  if i[0] not in blocked[i[1]]:
    blocked[i[1]].append(i[0])
  
for i in range(len(connected)):
  connected[i] = set(connected[i])
for i in range(len(blocked)):
  blocked[i] = set(blocked[i])
  
nCand = [0]*(nPerson+1)

def findCand(target,curPer):
  if visited[curPer] == True :
    return
  visited[curPer] = True
  if curPer not in connected[target] and curPer not in blocked[target]:
    nCand[target] += 1
  for i in connected[curPer]:
    findCand(target,i)

for i in range(1,nPerson+1):
  visited = [False]*(nPerson+1)
  visited[i] = True
  for j in connected[i]:
    findCand(i,j)

res = ""
for i in range(1,nPerson+1):
  res += str(nCand[i]) + " "
  
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n,m,k = map(int,input().split())
ans = [[0]*n for i in range(n)]

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

group = [-1]*n
def check():
    
    count = 1
    for i in range(n):
        if group[i] == -1:
            dfs(i,count)
            count += 1
    return group

def dfs(i,count):
    q = deque([])
    q.append(i)
    while q:
        bef = q.pop()

        for nex in fre[bef]:
            if group[nex] == -1:
                group[nex] = count
                q.append(nex)
    
check()
for i in range(n):
    if group[i] == -1:
        print(0,end=" ")
    else:
        num = group.count(group[i])
        num -= len(fre[i])
        for j in blo[i]:
            if group[j] == group[i]:
                num -= 1
        print(num-1,end=" ")

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m,k = map(int,input().split())
    # frend = [[10**6] * n for i in range(n)]
    # block = [[0] * n for i in range(n)]
    f = [[0]*n for i in range(n)]
    fq = []
    b = [[0]*n for i in range(n)]
    bq = []
    uf = UnionFind(n)
    for _ in range(m):
        a,bb = map(int,input().split())
        f[a-1][bb-1] = 1
        f[bb-1][a-1] = 1
        uf.union(a-1,bb-1)
        fq.append([a-1,bb-1])

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


    dame = [0] * n

    ans = [0]*n
    for i, ff in enumerate(fq):
        if uf.same(ff[0],ff[1]):
            dame[ff[0]] += 1
            dame[ff[1]] += 1

    for i, bb in enumerate(bq):
        if uf.same(bb[0],bb[1]):
            dame[bb[0]] += 1
            dame[bb[1]] += 1

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

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


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

line = input().split()
nPerson = int(line[0])
nFriend = int(line[1])
nBlock  = int(line[2])

friends = [[] for i in range(nFriend)]
for i in range(nFriend):
  line = input().split()
  friends[i] =[int(line[0]), int(line[1]) ]

blocks = [[] for i in range(nBlock)]
for i in range(nBlock):
  line = input().split()
  blocks[i] = [int(line[0]), int(line[1]) ]
  
connected = [[] for i in range(nPerson+1)]
  
for i in friends:
  connected[i[0]].append(i[1])
  connected[i[1]].append(i[0])

blocked = [[] for i in range(nPerson+1)]
for i in blocks:
  blocked[i[0]].append(i[1])
  blocked[i[1]].append(i[0])
  
for i in range(len(connected)):
  connected[i] = set(connected[i])
for i in range(len(blocked)):
  blocked[i] = set(blocked[i])
  
nCand = [0]*(nPerson+1)

def findCand(target,curPer):
  if visited[curPer] == True :
    return
  visited[curPer] = True
  if curPer not in connected[target] and curPer not in blocked[target]:
    nCand[target] += 1
  for i in connected[curPer]:
    findCand(target,i)

for i in range(1,nPerson+1):
  visited = [False]*(nPerson+1)
  visited[i] = True
  for j in connected[i]:
    findCand(i,j)

res = ""
for i in range(1,nPerson+1):
  res += str(nCand[i]) + " "
  
print(res)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
c=[list(map(int,input().split())) for i in range(k)]

lf=[[] for i in range(n)]
for i in range(m):
    lf[a[i][0]-1].append(a[i][1])
    lf[a[i][1]-1].append(a[i][0])
lb=[[]for i in range(n)]
for i in range(k):
    lb[c[i][0]-1].append(c[i][1])
    lb[c[i][1]-1].append(c[i][0])

lc=[[] for i in range(n)]
for i in range(m):
    lc[a[i][0]-1].append(a[i][1])
    lc[a[i][1]-1].append(a[i][0])


for i in range(n):
    l=set(lc[i])
    l.add(i+1)
    for j in lc[i]:
        for p in lf[j-1]:
            if p not in l:
                lc[i].append(p)
                l.add(p)


lm=[]
for i in range(n):
    lm.append(len(lc[i])-len(lf[i]))
    for j in lb[i]:
        if j in lc[i]:
            lm[i]-=1

for i in lm:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M, K = LI()
AB = []
CD = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append([a,b])
for k in range(K):
    c, d = LI()
    c -= 1
    d -= 1
    CD.append([c,d])

direct_friend = {}
blocked = {}
relation = [[] for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)

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

u = UnionFind(N)
for a,b in AB:
    u.Unite(a, b)

cluster = [[] for i in range(N)]
for n in range(N):
    cluster[u.Find_Root(n)].append(n)

for i in range(N):
    cluster[i] = set(cluster[i])

for c in cluster:
    for node in c:
        relation[node] = c

for i in range(N):
    direct_friend[i] = set(direct_friend[i])
    blocked[i] = set(blocked[i])

for i in range(N):
    print(len(relation[i] - direct_friend[i] - blocked[i]) - 1, end = " ")

print("")

"""
direct_friend = {}
blocked = {}
relation = [[] for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)

def dfs(node, p, cluster):
    cluster.append(node)
    if len(direct_friend[node]) == 1:
        return cluster
    for new_node in direct_friend[node]:
        if new_node == p:continue
        elif new_node in cluster:continue
        else:
            return dfs(new_node, node, cluster)

for i in range(N):
    if len(relation[i]) == 0:
        cluster = dfs(i, -1, [])
        # print(cluster)
        if cluster == None:
            relation[i] = []
        else:   
            for j in cluster:
                relation[j] = cluster

# print(relation)
# print(direct_friend)
# print(blocked)

for i in range(N):
    blocked[i] = set(blocked[i])
    direct_friend[i] = set(direct_friend[i])

# for i in range(N):
#     if len(direct_friend[n]) == 0:

ans = []
for n in range(N):
    ans.append(len(set(relation[n]) - direct_friend[n] - blocked[n] - set([n])))

for a in ans:
    print(a, end = " ")
print("")

"""