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
from collections import defaultdict as dd
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
    else:
        par[b]=a
        rank[a]+=rank[b]       
    return
 

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

par=(list(range(N+1))) ##union-findの親リスト
rank=[1]*(N+1) #unionの大きさ

p=[0]*(N+1) ##枝の数
for _ in range(M):
    A,B=map(int, input().split())
    p[A]+=1
    p[B]+=1
    union(A,B)
for i in range(1,N+1):
    par[i]=find(i)  ##union-find最終まとめ

fd=dd(list)   ##ブロック関係
for _ in range(K):
    C,D=map(int, input().split())
    fd[C].append(D)  ##ブロック関係をメモ
    fd[D].append(C)

ans=[0]*(N)
for i in range(1,N+1):
    ans[i-1]=par.count(par[i])-p[i]-1  ##自分と親が同じ数-枝-自分
    if len(fd[i])>0:
        for j in fd[i]:
            if par[i]==par[j]:
                ans[i-1]-=1  ##ブロック関係分を削除

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
    else:
        par[b]=a
        rank[a]+=rank[b]       

    return
 

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

par=(list(range(N+1))) ##union-findの親リスト
rank=[1]*(N+1) #unionの大きさ

p=[0]*(N+1)
for _ in range(M):
    A,B=map(int, input().split())
    p[A]+=1
    p[B]+=1
    union(A,B)

fd=dd(list)   ##ブロック関係
q=[0]*(N+1)
for _ in range(K):
    C,D=map(int, input().split())
    fd[C].append(D)  ##ブロック関係をメモ
    fd[D].append(C)

ans=[0]*(N)
for i in range(1,N+1):
    par[i]=find(i)  ##union-find最終まとめ
for i in range(1,N+1):
    ans[i-1]=par.count(par[i])-p[i]-1
    for j in fd[i]:
        if par[i]==par[j]:
            ans[i-1]-=1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
    else:
        par[b]=a
        rank[a]+=rank[b]       

    return
 

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

par=(list(range(N+1))) ##union-findの親リスト
rank=[1]*(N+1) #unionの大きさ

p=[0]*(N+1)
for _ in range(M):
    A,B=map(int, input().split())
    p[A]+=1
    p[B]+=1
    union(A,B)

fd=dd(list)   ##ブロック関係
q=[0]*(N+1)
for _ in range(K):
    C,D=map(int, input().split())
    fd[C].append(D)  ##ブロック関係をメモ
    fd[D].append(C)

fl=dd(list)  ##フレンド候補
             ##union-findで作成した集合をリスト化
ans=[0]*(N)
for i in range(1,N+1):
    par[i]=find(i)  ##union-find最終まとめ
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if par[i]==par[j]:
            fl[i].append(j)
            fl[j].append(i)
    for j in fd[i]:
        if j in fl[i]:
            fl[i].remove(j)
    ans[i-1]=len(fl[i])-p[i]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
sys.setrecursionlimit(10**8)

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
    else:
        par[b]=a
        rank[a]+=rank[b]       

    return
 

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

par=(list(range(N+1))) ##union-findの親リスト
rank=[1]*(N+1) #unionの大きさ

path=dd(list)  ##直接つながっている枝
for _ in range(M):
    A,B=map(int, input().split())
    path[A].append(B)
    path[B].append(A)
    union(A,B)

fd=dd(list)   ##ブロック関係
for _ in range(K):
    C,D=map(int, input().split())
    fd[C].append(D)  ##ブロック関係をメモ
    fd[D].append(C)

fl=dd(list)  ##フレンド候補
             ##union-findで作成した集合をリスト化
ans=[0]*(N)
for i in range(1,N+1):
    par[i]=find(i)  ##union-find最終まとめ
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if par[i]==par[j]:
            fl[i].append(j)
            fl[j].append(i)
    for j in fd[i]:
        if j in fl[i]:
            fl[i].remove(j)
    ans[i-1]=len(fl[i])-len(path[i])

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

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

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

def main():
    N, M, K = MI()
    uf = UnionFind(N)
    fri_list = defaultdict(None)
    blo_list = defaultdict(None)
    cnt_list = [0] * N
    for i in range(M):
        a, b = MI()
        a, b = a - 1, b - 1
        uf.union(a, b)
        fri_list[(a, b)] = 1
        fri_list[(b, a)] = 1
    for i in range(K):
        c, d = MI()
        c, d = c - 1, d - 1
        blo_list[(c, d)] = 1
        blo_list[(d, c)] = 1
    for i in range(N):
        cnt = uf.size(i)
        ans_list = uf.members(i)
        for ans in ans_list:
            if fri_list.get((i, ans)) == 1 or fri_list.get((ans, i)) == 1:
                cnt -= 1
            elif blo_list.get((i, ans)) == 1 or blo_list.get((ans, i)) == 1:
                cnt -= 1
        cnt -= 1
        cnt_list[i] = cnt
    print(' '.join(map(str, cnt_list)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

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

def main():
    N, M, K = MI()
    uf = UnionFind(N)
    fri_list = [[]for _ in range(N)]
    blo_list = [[]for _ in range(N)]
    cnt_list = [0] * N
    for i in range(M):
        a, b = MI()
        a, b = a - 1, b - 1
        uf.union(a, b)
        fri_list[a].append(b)
        fri_list[b].append(a)
    for i in range(K):
        c, d = MI()
        c, d = c - 1, d - 1
        blo_list[c].append(d)
        blo_list[d].append(c)
    for i in range(N):
        cnt = uf.size(i)
        ans_list = uf.members(i)
        for ans in ans_list:
            if ans in fri_list[i]:
                cnt -= 1
            elif ans in blo_list[i]:
                cnt -= 1
        cnt -= 1
        cnt_list[i] = cnt
    print(' '.join(map(str, cnt_list)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m,k = map(int,input().split())
f = []
h = []
t = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  f.append((a,b))
  t[a].append(b)
  t[b].append(a)
for _ in range(k):
  a,b = map(lambda x:int(x)-1,input().split())
  h.append((a,b))
c = [False]*n

def dfs(d):
  c[d] = True
  ret=[]
  for i in t[d]:
    if not c[i]:
      ret += dfs(i)
  return [d] + ret

ans = [[] for _ in range(n)]
for i in range(n):
  if not c[i]:
    e = dfs(i)
    for j in e:
      ans[j] = list(e)
      ans[j].remove(j)
for i,j in f:
  ans[i].remove(j)
  ans[j].remove(i)
for i,j in h:
  if j in ans[i]:
    ans[i].remove(j)
  if i in ans[j]:
    ans[j].remove(i)
print(*map(len,ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m,k = map(int,input().split())
f = []
h = []
t = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  f.append((a,b))
  t[a].append(b)
  t[b].append(a)
for _ in range(k):
  a,b = map(lambda x:int(x)-1,input().split())
  h.append((a,b))
ans = [0]*n
c = [False]*n

def dfs(d):
  c[d] = True
  ret=[]
  for i in t[d]:
    if not c[i]:
      ret += dfs(i)
  return [d] + ret
m = []
for i in range(n):
  if not c[i]:
    e = dfs(i)
    g = len(e)-1
    if g > 1:
      m.append(set(e))
    for j in e:
      ans[j] = g
for i,j in f:
  ans[i]-=1
  ans[j]-=1
for i,j in h:
  for k in m:
    o = len(k & set((i,j)))
    if o == 2:
      ans[i]-=1
      ans[j]-=1
      break
    elif o == 1:
      break
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m,k = map(int,input().split())
f = []
h = []
t = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  f.append((a,b))
  t[a].append(b)
  t[b].append(a)
for _ in range(k):
  a,b = map(lambda x:int(x)-1,input().split())
  h.append((a,b))
ans = [0]*n
c = [False]*n

def dfs(d):
  c[d] = True
  ret=[]
  for i in t[d]:
    if not c[i]:
      ret += dfs(i)
  return [d] + ret
m = []
for i in range(n):
  if not c[i]:
    e = dfs(i)
    m.append(set(e))
    g = len(e)-1
    for j in e:
      ans[j] = g
for i,j in f:
  ans[i]-=1
  ans[j]-=1
for i,j in h:
  for k in m:
    o = len(k & set((i,j)))
    if o == 2:
      ans[i]-=1
      ans[j]-=1
      break
    elif o == 1:
      break
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m, k = map(int, input().split())
f = [set() for _ in range(n)]
l = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    f[a].add(b)
    f[b].add(a)
for _ in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    l[d].add(c)
    l[c].add(d)

q = deque()
ans = [0] * n
for i in range(n):
    e = [0] * n
    z = [0] * n
    e[i] = 1
    for j in f[i]:
        q.appendleft(j)
        e[j] = 1
    for j in l[i]:
        z[j] = 1
    while q:
        v = q.pop()
        for j in f[v]:
            if e[j] == 0:
                q.appendleft(j)
                e[j] = 1
                if z[j] == 0:
                    ans[i] += 1
print(' '.join(list(map(str, ans))))

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def 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=UnionFind(N)
not_friend_candidates=[]

for i in range(M):
  A,B=list(map(int,input().split()))
  A-=1
  B-=1
  tree.union(A,B)
  not_friend_candidates.append([A,B])

for j in range(K):
  C,D=list(map(int,input().split()))
  C-=1
  D-=1
  not_friend_candidates.append([C,D])

all_group_members=tree.all_group_members()

ans=[0]*N
for i,j in not_friend_candidates:
  if tree.same(i,j):
    ans[i]-=1
    ans[j]-=1
for i in range(N):
  ans[i]+=len(all_group_members[tree.find(i)])-1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M,K = list(map(int,input().split()))
G1 = [[] for i in range(N)]
G2 = [[] for i in range(N)]
for i in range(M):
    A,B = list(map(int,input().split()))
    G1[A-1].append(B-1)
    G1[B-1].append(A-1)

for i in range(K):
    A,B = list(map(int,input().split()))
    G2[A-1].append(B-1)
    G2[B-1].append(A-1)

Block = [0]*N
Friend = [0]*N
Network = [0]*N
out = [0]*N

for i in range(N):
    Friend[i] = len(G1[i])

Done = [0]*N
for i in range(N):
    s = i
    if Done[s]!=0:
        continue
    L = []
    que = deque([s])
    Done[s] = 1
    L.append(s)
    while que:
        v = que.popleft()
        for w in G1[v]:
            if Done[w]==1:
                continue
            Done[w] = 1
            que.append(w)
            L.append(w)
    NL = len(L)
    for j in L:
        Network[j] = NL-1
        Block[j] = len(set(L)&set(G2[j]))

for i in range(N):
    out[i] = Network[i]-Block[i]-Friend[i]
print(*out)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m,k=map(int,input().split())
friend=[[] for _ in range(n)]
block=[[False]*n for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friend[a].append(b)
    friend[b].append(a)
for _ in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    block[c][d]=True
    block[d][c]=True

def dfs(graph,v,s):
    seen[v]=True
    if not block[s][v]:
        count[s]+=1
    for nv in graph[v]:
        if seen[nv]:
            continue
        dfs(graph,nv,s)
count=[0]*n
for v in range(n):
    seen=[False]*n
    temp=0
    if seen[v]:
        continue
    dfs(friend,v,v)
    count[v]-=1
    count[v]-=len(friend[v])

for i in range(n):
    print(count[i],end=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):	#初期化
        self.n = n
        self.parents = [-1] * n
    def find(self, x):		#属すグループの根(リーダー)
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):	#連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):		#同じグループに属す頂点数
        return -self.parents[self.find(x)]
    def same(self, x, y):	#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())
suggest = UnionFind(n)
follow = [0]*n
block = [0]*n
for i in range(n):
    follow[i] = list()
    block[i]  = list()
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    suggest.union(a,b)
    follow[a].append(b)
    follow[b].append(a)

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    block[c].append(d)
    block[d].append(c)
ans = ""
suggestfriend = [0]*n
for i in range(n):
    count = 0
    for j in range(i,n):
        if(i != j):
            if (not(j in follow[i]) and not(j in block[i])):
                # print(suggest.same(i,j))
                if(suggest.same(i,j)):
                    count += 1
                    suggestfriend[j] += 1
    count += suggestfriend[i]
    ans += str(count) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):	#初期化
        self.n = n
        self.parents = [-1] * n
    def find(self, x):		#属すグループの根(リーダー)
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):	#連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):		#同じグループに属す頂点数
        return -self.parents[self.find(x)]
    def same(self, x, y):	#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())
suggest = UnionFind(n)
follow = [0]*n
block = [0]*n
for i in range(n):
    follow[i] = [0]*n
    block[i]  = [0]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    suggest.union(a,b)
    follow[a][b] = 1
    follow[b][a] = 1

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    block[c][d] = 1
    block[d][c] = 1
ans = ""
suggestfriend = [0]*n

for i in range(n):
    count = 0
    for j in range(i,n):
        if(i != j):
            if (follow[i][j] == 0 and block[i][j] == 0):
                # print(suggest.same(i,j))
                if(suggest.same(i,j)):
                    count += 1
                    suggestfriend[j] += 1
    count += suggestfriend[i]
    ans += str(count) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):	#初期化
        self.n = n
        self.parents = [-1] * n
    def find(self, x):		#属すグループの根(リーダー)
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):	#連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):		#同じグループに属す頂点数
        return -self.parents[self.find(x)]
    def same(self, x, y):	#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())
suggest = UnionFind(n)
follow = [0]*n
block = [0]*n
for i in range(n):
    follow[i] = [0]*n
    block[i]  = [0]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    suggest.union(a,b)
    follow[a][b] = 1
    follow[b][a] = 1

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    block[c][d] = 1
    block[d][c] = 1
ans = ""
for i in range(n):
    count = 0
    for j in range(n):
        if(i != j):
            if (follow[i][j] == 0 and block[i][j] == 0):
                # print(suggest.same(i,j))
                if(suggest.same(i,j)):
                    count += 1
    ans += str(count) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):	#初期化
        self.n = n
        self.parents = [-1] * n
    def find(self, x):		#属すグループの根(リーダー)
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):	#連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):		#同じグループに属す頂点数
        return -self.parents[self.find(x)]
    def same(self, x, y):	#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())
suggest = UnionFind(n)
follow = [0]*n
block = [0]*n
for i in range(n):
    follow[i] = list()
    block[i]  = list()
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    suggest.union(a,b)
    follow[a].append(b)
    follow[b].append(a)

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    block[c].append(d)
    block[d].append(c)
ans = ""
for i in range(n):
    count = 0
    for j in range(n):
        if(i != j):
            if (not(j in follow[i]) and not(j in block[i])):
                # print(suggest.same(i,j))
                if(suggest.same(i,j)):
                    count += 1
    ans += str(count) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


class People:
    def __init__(self):
        self.frends = 0
        self.blocks = 0


n, m, k = [int(i) for i in input().split()]

data=[1]*m
row=[]
col=[]
peoples = [People() for i in range(n + 1)]
for i in range(m):
    one, two = [int(j) for j in input().split()]
    new_one=min(one,two)
    new_two=max(one,two)
    row.append(one)
    col.append(two)
    peoples[one].frends+=1
    peoples[two].frends+=1

frends = csr_matrix((data, (row, col)), shape=(n+1, n+1))


num, labels = connected_components(frends)
labels=list(labels)

for i in range(k):
    one, two = [int(j) for j in input().split()]
    if labels[one] == labels[two]:
        peoples[one].blocks+=1
        peoples[two].blocks+=1

renketu_num = [0]
for i in range(1, num + 1):
    renketu_num.append(labels.count(i))


def get_renketu_num(i):
    return renketu_num[labels[i]] - 1


def get_friend_num(i):
    return peoples[i].frends


def get_block_num(i):
    return peoples[i].blocks


for i in range(1, n + 1):
    print(get_renketu_num(i) - get_friend_num(i) - get_block_num(i))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


class People:
    def __init__(self):
        self.frends = 0
        self.blocks = 0


n, m, k = [int(i) for i in input().split()]

data=[1]*(2*m)
row=[]
col=[]
peoples = [People() for i in range(n + 1)]
for i in range(m):
    one, two = [int(j) for j in input().split()]
    row.append(one)
    row.append(two)
    col.append(two)
    col.append(one)
    peoples[one].frends+=1
    peoples[two].frends+=1

frends = csr_matrix((data, (row, col)), shape=(n+1, n+1))


num, labels = connected_components(frends)
labels=list(labels)

for i in range(k):
    one, two = [int(j) for j in input().split()]
    if labels[one] == labels[two]:
        peoples[one].blocks+=1
        peoples[two].blocks+=1

renketu_num = [0]
for i in range(1, num + 1):
    renketu_num.append(labels.count(i))


def get_renketu_num(i):
    return renketu_num[labels[i]] - 1


def get_friend_num(i):
    return peoples[i].frends


def get_block_num(i):
    return peoples[i].blocks


for i in range(1, n + 1):
    print(get_renketu_num(i) - get_friend_num(i) - get_block_num(i))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


class People:
    def __init__(self):
        self.frends = []
        self.blocks = []


n, m, k = [int(i) for i in input().split()]

data=[1]*(2*m)
row=[]
col=[]
peoples = [People() for i in range(n + 1)]
for i in range(m):
    one, two = [int(j) for j in input().split()]
    row.append(one)
    row.append(two)
    col.append(two)
    col.append(one)
    peoples[one].frends.append(two)
    peoples[two].frends.append(one)

frends = csr_matrix((data, (row, col)), shape=(n+1, n+1))


num, labels = connected_components(frends)
labels=list(labels)

for i in range(k):
    one, two = [int(j) for j in input().split()]
    if labels[one] == labels[two]:
        peoples[one].blocks.append(two)
        peoples[two].blocks.append(one)

renketu_num = [0]
for i in range(1, num + 1):
    renketu_num.append(labels.count(i))


def get_renketu_num(i):
    return renketu_num[labels[i]] - 1


def get_friend_num(i):
    return len(peoples[i].frends)


def get_block_num(i):
    return len(peoples[i].blocks)


for i in range(1, n + 1):
    print(get_renketu_num(i) - get_friend_num(i) - get_block_num(i))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import connected_components


class People:
    def __init__(self):
        self.frends = []
        self.blocks = []


n, m, k = [int(i) for i in input().split()]

frends = lil_matrix((n + 1, n + 1), dtype=int)
peoples = [People() for i in range(n + 1)]

for i in range(m):
    one, two = [int(j) for j in input().split()]
    frends[one, two] = 1
    frends[two, one] = 1
    peoples[one].frends.append(two)
    peoples[two].frends.append(one)
num, labels = connected_components(frends)
labels=list(labels)

for i in range(k):
    one, two = [int(j) for j in input().split()]
    if labels[one] == labels[two]:
        peoples[one].blocks.append(two)
        peoples[two].blocks.append(one)

renketu_num = [0]
for i in range(1, num + 1):
    renketu_num.append(labels.count(i))


def get_renketu_num(i):
    return renketu_num[labels[i]] - 1


def get_friend_num(i):
    return len(peoples[i].frends)


def get_block_num(i):
    return len(peoples[i].blocks)


for i in range(1, n + 1):
    print(get_renketu_num(i) - get_friend_num(i) - get_block_num(i))