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:
import sys
input = sys.stdin.buffer.readline

def main():
    n, m, k = map(int, input().split())
    parent_f = list(range(n+1))
    rank_f = [0]*(n+1)
    parent_b = list(range(n+1))
    rank_b = [0]*(n+1)
    group_f = [set() for _ in range(n+1)]
    group_b = [set() for _ in range(n+1)]
    group_index_f = [None]*(n+1)
    group_index_b = [None]*(n+1)
    friends = [set() for i in range(n+1)]
    blocks = [set() for i in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a] |= {b}
        friends[b] |= {a}
        unite(a, b, parent_f, rank_f)
    for _ in range(k):
        c, d = map(int, input().split())
        blocks[c] |= {d}
        blocks[d] |= {c}
        unite(c, d, parent_b, rank_b)
    for i in range(1, n+1):
        rf = root(i, parent_f)
        rb = root(i, parent_b)
        group_f[rf] |= {i}
        group_b[rb] |= {i}
        group_index_f[i] = rf
        group_index_b[i] = rb
    for i in range(1, n+1):
        print(len(group_f[group_index_f[i]]-friends[i]-blocks[i]-{i}))
    
    

def root(x, parent):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x], parent)
    return parent[x]

def unite(x, y, parent, rank):
    x = root(x, parent)
    y = root(y, parent)
    if x != y:
        if rank[x] > rank[y]:
            parent[y] = x
        elif rank[x] < rank[y]:
            parent[x] = y
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4100000)

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

#友達関係
F = [deque([]) for i in range(n)] #Friend
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
gid = 0 #group id

#DFSを行うための関数
def using_DFS(p):
    if G[p] == 0:
        G[p] = gid
        for j in F[p]:
            if G[j-1] == 0:
                using_DFS(j-1)
            else:   #すでに登場
                pass
    else:
        pass

for i in range(n):
    if G[i] == 0:
        gid += 1
        using_DFS(i)
    else:
        pass
#print('G=',G)
#print('S=',S)

#ブロック関係
BinG = [deque([]) for i in range(n)] #Block in Group
for i in range(k):
    c, d = map(int, input().split())
    if G[c-1] == G[d-1]:
        BinG[c-1].append(d)
        BinG[d-1].append(c)
    else:
        pass
#print('F=',F)
#print('B=',B)

for i in range(n):
    ans = G.count(G[i]) - 1 - len(F[i]) - len(BinG[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4100000)

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

#友達関係
F = [deque([]) for i in range(n)] #Friend
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
GS = deque([])   #Group Size
gid = 0 #group id

#DFSを行うための関数
def using_DFS(p):
    if G[p] == 0:
        G[p] = gid
        for j in F[p]:
            if G[j-1] == 0:
                using_DFS(j-1)
            else:   #すでに登場
                pass
    else:
        pass

for i in range(n):
    if G[i] == 0:
        gid += 1
        t = 0
        using_DFS(i)
        GS.append(G.count(gid))
    else:
        pass
#print('G=',G)
#print('S=',S)

#ブロック関係
BinG = [deque([]) for i in range(n)] #Block in Group
for i in range(k):
    c, d = map(int, input().split())
    if G[c-1] == G[d-1]:
        BinG[c-1].append(d)
        BinG[d-1].append(c)
    else:
        pass
#print('F=',F)
#print('B=',B)

for i in range(n):
    ans = GS[G[i]-1] - 1 - len(F[i]) - len(BinG[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

n, m, k = map(int, input().split())
F = [[] for i in range(n)] #Friend
BinG = [[] for i in range(n)] #Block in Group
#友達関係
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
GS = []   #Group Size
gid = 0 #group id

#DFSを行うための関数
def using_DFS(p):
    if G[p] == 0:
        G[p] = gid
        for j in F[p]:
            if G[j-1] == 0:
                using_DFS(j-1)
            else:   #すでに登場
                pass
    else:
        pass

for i in range(n):
    if G[i] == 0:
        gid += 1
        t = 0
        using_DFS(i)
        GS.append(G.count(gid))
    else:
        pass
#print('G=',G)
#print('S=',S)

#ブロック関係
for i in range(k):
    c, d = map(int, input().split())
    if G[c-1] == G[d-1]:
        BinG[c-1].append(d)
        BinG[d-1].append(c)
    else:
        pass
#print('F=',F)
#print('B=',B)

for i in range(n):
    ans = GS[G[i]-1] - 1 - len(F[i]) - len(BinG[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4100000)
n, m, k = map(int, input().split())
F = [deque([]) for i in range(n)] #Friend
B = [deque([]) for i in range(n)] #Block
#友達関係
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#ブロック関係
for i in range(k):
    c, d = map(int, input().split())
    B[c-1].append(d)
    B[d-1].append(c)
#print('F=',F)
#print('B=',B)

def using_DFS(p):
    if G[p] == 0:
        G[p] = num
        for j in F[p]:
            if G[j-1] == 0:
                using_DFS(j-1)
            else:   #すでに登場
                pass
    else:
        pass

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
S = deque([])   #Size
num = 0
for i in range(n):
    if G[i] == 0:
        num += 1
        t = 0
        using_DFS(i)
        S.append(G.count(num))
    else:
        pass
#print('G=',G)
#print('S=',S)

#答えの計算
for i in range(n):
    ans = S[G[i]-1] - 1
    #ブロック関係がこの中で何人いるか
    for j in B[i]:
        if G[j-1] == G[i]:
            ans -= 1
        else:
            pass
    #直接の友達関係がこの中で何人いるか
    for k in F[i]:
        if G[k-1] == G[i]:
            ans -= 1
        else:
            pass
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(4100000)
n, m, k = map(int, input().split())
F = [deque([]) for i in range(n)] #Friend
B = [deque([]) for i in range(n)] #Block
#友達関係
for i in range(m):
    a, b = map(int, input().split())
    F[a-1].append(b)
    F[b-1].append(a)

#ブロック関係
for i in range(k):
    c, d = map(int, input().split())
    B[c-1].append(d)
    B[d-1].append(c)
#print('F=',F)
#print('B=',B)

def using_DFS(p):
    if G[p] == 0:
        G[p] = num
        for j in F[p]:
            using_DFS(j-1)
    else:
        pass

#DFSで連結部分ごとのグループに分ける
G = [0] * n #Group
S = deque([])   #Size
num = 0
for i in range(n):
    if G[i] == 0:
        num += 1
        t = 0
        using_DFS(i)
        S.append(G.count(num))
    else:
        pass
#print('G=',G)
#print('S=',S)

#答えの計算
for i in range(n):
    ans = S[G[i]-1] - 1
    #ブロック関係がこの中で何人いるか
    for j in B[i]:
        if G[j-1] == G[i]:
            ans -= 1
        else:
            pass
    #直接の友達関係がこの中で何人いるか
    for k in F[i]:
        if G[k-1] == G[i]:
            ans -= 1
        else:
            pass
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

for _ in range(k):
    a,b=map(int,input().split())
    block[a].add(b)
    block[b].add(a)


checked=set([])
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.add(i)
        group=set([i])
        bf=set([i])
        while len(group)!= 0:
            temp=group.pop()
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.add(item)
                    bf.add(item)
        lenbf=len(bf)
        for item1 in bf:
            bl=0
            for item2 in bf:
                if item2 in block[item1]:
                    bl+=1
            result[item1-1]=lenbf-1-len(list(friend[item1]))-bl



        bfbf.append(bf)
result=list(map(str,result))
print(" ".join(result))

Submission status: Time Limit Exceeded

Solution code:

#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

for _ in range(k):
    a,b=map(int,input().split())
    block[a].add(b)
    block[b].add(a)


checked=set([])
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.add(i)
        group=[i]
        bf=[i]
        while len(group)!= 0:
            temp=group.pop(0)
            for item in friend[temp]:
                if item not in checked:
                    checked.add(item)
                    group.append(item)
                    bf.append(item)
        lenbf=len(bf)
        for item1 in bf:
            bl=0
            for item2 in bf:
                if item2 in block[item1]:
                    bl+=1
            result[item1-1]=lenbf-1-len(list(friend[item1]))-bl



        bfbf.append(bf)
result=list(map(str,result))
print(" ".join(result))

Submission status: Time Limit Exceeded

Solution code:

#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

for _ in range(k):
    a,b=map(int,input().split())
    block[a].add(b)
    block[b].add(a)


checked=[]
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.append(i)
        group=[i]
        bf=[i]
        while len(group)!= 0:
            temp=group.pop(0)
            for item in friend[temp]:
                if item not in checked:
                    checked.append(item)
                    group.append(item)
                    bf.append(item)
        lenbf=len(bf)
        for item1 in bf:
            bl=0
            for item2 in bf:
                if item2 in block[item1]:
                    bl+=1
            result[item1-1]=lenbf-1-len(list(friend[item1]))-bl



        bfbf.append(bf)
result=list(map(str,result))
print(" ".join(result))

Submission status: Time Limit Exceeded

Solution code:

#n:
#m:
#k:
n,m,k=map(int,input().split())
friend={}
block={}
result=[]
for i in range(1,n+1):
    friend[i]=set([])
    block[i]=set([])
    result.append(0)

for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

for _ in range(k):
    a,b=map(int,input().split())
    block[a].add(b)
    block[b].add(a)


checked=[]
bfbf=[]
for i in range(1,n+1):
    #print(i,checked)
    if i not in checked:
        checked.append(i)
        group=[i]
        bf=[i]
        while len(group)!= 0:
            temp=group.pop(0)
            for item in friend[temp]:
                if item not in checked:
                    checked.append(item)
                    group.append(item)
                    bf.append(item)
        for item1 in bf:
            bl=0
            for item2 in bf:
                if item2 in block[item1]:
                    bl+=1
            result[item1-1]=len(bf)-1-len(list(friend[item1]))-bl



        bfbf.append(bf)
result=list(map(str,result))
print(" ".join(result))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():

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

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

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

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


n, m, k = map(int, input().split())
friend_cand = UnionFind(n)
friend = {i: set() for i in range(n)}
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friend[a].add(b)
    friend[b].add(a)
    friend_cand.unite(a, b)
block = {i: set() for i in range(n)}
for _ in range(k):
    c, d = map(lambda x: int(x)-1, input().split())
    block[c].add(d)
    block[d].add(c)

res = []
for i in range(n):
    friend_cnt = block_cnt = 0
    for k in friend_cand.members(i):
        if k in friend[i]:
            friend_cnt += 1
        elif k in block[i]:
            block_cnt += 1
    res.append(friend_cand.size(i) - friend_cnt - block_cnt - 1)

print(' '.join(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]
 #xのグループとyのグループを結合
    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_groupmembers(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)
friend_count=[0]*N
for m in range(M):
    p,q = map(int, input().split())
    friend_count[p-1]+=1
    friend_count[q-1]+=1
    uf.union(p-1, q-1)
to=[[] for i in range(N)]
for i in range(K):
    a,b=map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
allg =  uf.all_groupmembers()
last_list=[]
for n in range(N):
    leng = uf.size(n)
    for j in to[n]:
        if(uf.same(n,j)):leng-=1
    print(str(leng-1-friend_count[n]), 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]
 #xのグループとyのグループを結合
    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_groupmembers(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)
friend_count=[0]*N
for m in range(M):
    p,q = map(int, input().split())
    friend_count[p-1]+=1
    friend_count[q-1]+=1
    uf.union(p-1, q-1)
bgraph = {}
for k in range(K):
    p,q = map(int, input().split())
    if p-1 in bgraph.keys():
        bgraph[p-1].append(q-1)
    else:
        bgraph[p-1] = [q-1]
    if q-1 in bgraph.keys():
        bgraph[q-1].append(p-1)
    else:
        bgraph[q-1] = [p-1]
allg =  uf.all_groupmembers()
last_list=[]
for n in range(N):
    leng = uf.size(n)
    if n in bgraph.keys():
        ng = len(set(bgraph[n])&set(uf.members(n)))
    else:
        ng = 0
    last_list.append(str(leng-ng-1-friend_count[n]))
    print(str(leng-ng-1-friend_count[n]), 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]
 #xのグループとyのグループを結合
    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_groupmembers(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)
friend_count=[0]*N
for m in range(M):
    p,q = map(int, input().split())
    friend_count[p-1]+=1
    friend_count[q-1]+=1
    uf.union(p-1, q-1)
bgraph = {}
for k in range(K):
    p,q = map(int, input().split())
    if p-1 in bgraph.keys():
        bgraph[p-1].append(q-1)
    else:
        bgraph[p-1] = [q-1]
    if q-1 in bgraph.keys():
        bgraph[q-1].append(p-1)
    else:
        bgraph[q-1] = [p-1]
allg =  uf.all_groupmembers()
last_list=[]
for n in range(N):
    for a in allg.values():
        if n in a:
            leng = len(a)
            if n in bgraph.keys():
                ng = len(set(bgraph[n])&set(a))
            else:
                ng = 0
            print(str(leng-ng-1-friend_count[n]), 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]
 #xのグループとyのグループを結合
    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_groupmembers(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)
friend_count=[0]*N
for m in range(M):
    p,q = map(int, input().split())
    friend_count[p-1]+=1
    friend_count[q-1]+=1
    uf.union(p-1, q-1)
bgraph = {}
for k in range(K):
    p,q = map(int, input().split())
    if p-1 in bgraph.keys():
        bgraph[p-1].append(q-1)
    else:
        bgraph[p-1] = [q-1]
    if q-1 in bgraph.keys():
        bgraph[q-1].append(p-1)
    else:
        bgraph[q-1] = [p-1]
allg =  uf.all_groupmembers()
last_list=[]
for n in range(N):
    for a in allg.values():
        if n in a:
            leng = len(a)
            if n in bgraph.keys():
                ng = len(set(bgraph[n])&set(a))
            else:
                ng = 0
            last_list.append(str(leng-ng-1-friend_count[n]))
print(" ".join(last_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#https://atcoder.jp/contests/abc157/tasks/abc157_d
n,m,k=mii()
arra=[[] for i in range(n)]
arrc=[[] for i in range(n)]

for i in range(m):
    a,b=mii()
    arra[a-1].append(b-1)
    arra[b-1].append(a-1)
for i in range(k):
    a,b=mii()
    arrc[a-1].append(b-1)
    arrc[b-1].append(a-1)

cnt=0
seen=[0]*n
for i in range(n):
    if seen[i]==0:
        cnt+=1
        seen[i]+=cnt
        task=deque(arra[i])
        while len(list(task))!=0:
            temp = task.popleft()
            if seen[temp]==0:
                seen[temp]+=cnt
                for i in arra[temp]:
                    if seen[i]==0:
                        task.appendleft(i)
#print(seen)
arrcnt=Counter(seen)
#print(arrcnt)
ans=[]
for i in range(n):
    cntarrc=0
    for j in arrc[i]:
        if seen[i]==seen[j]:
            cntarrc+=1
    #print(arrcnt[seen[i]],len(arrc[i]),len(arra[i]))
    ans.append(arrcnt[seen[i]] - cntarrc - len(arra[i])-1)
print(*ans)

Submission status: Time Limit Exceeded

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


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


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

    d = {i:set() for i in range(1, N+1)}
    block = {i:set() for i in range(1, N+1)}
    candidate = {i:set() for i in range(1, N+1)}

    uft = UnionFind(N)

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        block[C].add(D)
        block[D].add(C)

    for i in range(1, N+1):
        cd = set(range(i+1, N+1))-d[i]-block[i]
        for j in cd:
            if uft.isunited(i, j):
                candidate[i].add(j)
                candidate[j].add(i)

    print(*map(len, candidate.values()))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


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

    d = {i:set() for i in range(1, N+1)}
    block = {i:set() for i in range(1, N+1)}
    candidate = {i:set() for i in range(1, N+1)}

    uft = UnionFind(N)

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].add(B)
        d[B].add(A)
        uft.unite(A, B)

    for _ in range(K):
        C, D = map(int, input().split())
        block[C].add(D)
        block[D].add(C)

    for i in range(1, N+1):
        cd = set(range(1, N+1))-d[i]
        for j in cd:
            if i>=j:continue
            if uft.isunited(i, j) and not j in block[i]:
                candidate[i].add(j)
                candidate[j].add(i)

    print(*map(len, candidate.values()))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

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

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

  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    if x == y:
      return
    if self.ranks[x] < self.ranks[y]:
      self.parents[x] = y
    else:
      self.parents[y] = x
      if self.ranks[x] == self.ranks[y]:
        self.ranks[x] += 1

n, m, k = map(int, input().split())
u = UnionFind(n)
allusers = {i for i in range(n)}
users = [set() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  users[a - 1].add(b - 1)
  users[b - 1].add(a - 1)
  u.unite(a - 1, b - 1)
for _ in range(k):
  a, b = map(int, input().split())
  users[a - 1].add(b - 1)
  users[b - 1].add(a - 1)

print(*[len([i for cand in allusers - users[i] if u.same(i, cand)]) - 1 for i in range(n)])