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

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

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

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

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

    def roots(self):
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

    u = UnionFind(n)

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

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

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


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


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

main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 
 
n, m, k = map(int,input().split())
friends=[0]*n
uf = UnionFind(n)
for i in range(m):
    a, b = map(int,input().split())
    uf.union(a-1, b-1)
    friends[a-1]+=1
    friends[b-1]+=1
 
nowlist=list(uf.all_group_members().values())
 
koho=[0]*n
group=[0]*n
number=1
for nl in nowlist:
    ng=len(nl)
    for nnl in nl:
        koho[nnl]=ng
        group[nnl]=number
    number+=1
 
for i in range(k):
    c, d = map(int,input().split())
    if group[c-1]==group[d-1]:
        koho[c-1]-=1
        koho[d-1]-=1
 
for i in range(n):
    print(koho[i]-friends[i]-1, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


friendship = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    if a in friendship.keys():
        friendship[a].append(b)
    else:
        friendship[a] = [b]
        
    if b in friendship.keys():
        friendship[b].append(a)
    else:
        friendship[b] = [a]
        
block = {}
for j in range(k):
    c, d = list(map(int, input().split()))
    if c in block.keys():
        block[c].append(d)
    else:
        block[c] = [d]
        
    if d in block.keys():
        block[d].append(c)
    else:
        block[d] = [c]
        
ans = [0] * n
for i in range(n):
    person = i+1
    for j in range(n):
        if i <= j:
            continue
        target = j+1
        if person in friendship.keys():
            if target in friendship[person]:
                continue
        else:
            continue
        
        if person in block.keys():
            if target in block[person]:
                continue
        continue_flag = True
        checked_person = set()
        candidate = deque(friendship[person])
        while len(candidate)>0:
            c = deque.popleft(candidate)
            if c in friendship.keys():
                for p in friendship[c]:
                    if p == target:
                        ans[i] += 1
                        ans[j] += 1
                        checked_person.add(p)
                        continue_flag = False
                        break
                    else:
                        if p not in checked_person:
                            candidate.append(p)
                            checked_person.add(p)
                if continue_flag == False:
                    break
                
answer = ''
for i in range(len(ans)):
    answer += str(ans[i])
    if i != n-1:
        answer += ' '
            
print(answer)

Submission status: Time Limit Exceeded

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

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

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

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

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



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

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



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

kouho = [0]*N

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

class Dijkstra(object):
    def calc(self, graph, start, goal=None):
        num = len(graph)
        dist = [float('inf') for i in range(num)]
        prev = [float('inf') for i in range(num)]
        dist[start] = 0
        q = []
        heapq.heappush(q, (0, start))
        while len(q) != 0:
            prov_cost, src = heapq.heappop(q)
            if dist[src] < prov_cost:
                continue

            for dest in range(num):
                cost = graph[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(q, (dist[dest], dest))
                    prev[dest] = src
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]
        return list(reversed(path))

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq
friend_dict = {}
block_dict = {}
n, m, k = map(int, input().split())

class Dijkstra:
  def __init__(self):
    self.e = collections.defaultdict(list)

  def add(self, u, v, d):
    self.e[u].append([v, d])
    self.e[v].append([u, d])

  def search(self, s):
    """
    :param s: 始点
    :return: 始点から各点までの最短経路
    """
    d = collections.defaultdict(lambda: float('inf'))
    d[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    v = collections.defaultdict(bool)
    while len(q):
      k, u = heapq.heappop(q)
      if v[u]:
        continue
      v[u] = True

      for uv, ud in self.e[u]:
        if v[uv]:
          continue
        vd = k + ud
        if d[uv] > vd:
          d[uv] = vd
          heapq.heappush(q, (vd, uv))
    return d

G = Dijkstra()
  
for i in range(m):
  a, b = map(int, input().split())
  G.add(a, b, 1)
  if a not in friend_dict:
    friend_dict[a] = [b]
  else:
    friend_dict[a].append(b)
  if b not in friend_dict:
    friend_dict[b] = [a]
  else:
    friend_dict[b].append(a)
for i in range(k):
  a, b = map(int, input().split())
  if a not in block_dict:
    block_dict[a] = [b]
  else:
    block_dict[a].append(b)
  if b not in block_dict:
    block_dict[b] = [a]
  else:
    block_dict[b].append(a)

res_list = []
for i in range(n):
  res = 0
  node = i + 1
  block_list = block_dict.get(node, [])
  for k, v in G.search(node).items():
    # print("{}->{} length is {}".format(node, k, v))
    if k in block_list:
      continue
    if v > 1:
      res += 1
  res_list.append(str(res))
print(" ".join(res_list))

Submission status: Time Limit Exceeded

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

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

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

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

        if x == y:
            return

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

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

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf_friend = UnionFind(N)

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

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

ans = [0 for _ in range(N)]
for root in uf_friend.roots():
    m = uf_friend.members(root)
    l = len(uf_friend.members(root))
    for i in range(l):
        for j in range(i+1, l):
            # if es_friend[m[i]][m[j]] == es_block[m[i]][m[j]] == False:
            if m[j] not in es_friend[m[i]] and m[j] not in es_block[m[i]]:
                ans[m[i]] += 1
                ans[m[j]] += 1
print(" ".join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from bisect import bisect

def resolve():
    def find(i):
        x = S[i]
        while True:
            k = S[i][0]
            if k == i:
                x[0] = i
                return i
            S[i] = x
            i = k
    def join(i, j):
        ai = find(i)
        aj = find(j)
        if ai != aj:
            #S[aj][0] = S[ai][0]
            S[aj] = S[ai]
    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj

    N, M, K = iim()
    S = [[i] for i in range(N+1)]
    mk = set()
    for i in range(M):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        join(ai, bi)
        mk.add((ai, bi))
    for i in range(K):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        mk.add((ai, bi))

    ans = [0] * (N+1)
    #print(S)
    for i in range(1, N):
        aa = 0
        for j in range(i+1, N+1):
            if (i, j) in mk:
                continue
            if same(i, j):
                ans[i] += 1
                ans[j] += 1
    print(*ans[1:])



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
class UnionFindWithRank(object):
    par = []
    rank = []
    cache = True
    log = []

    def __init__(self, n):
        for i in range(n):
            self.par.append(i)
            self.rank.append(0)

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            p = self.root(self.par[x])
            self.par[x] = p
            return p

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

    def unite(self, x, y):
        ox, oy = x, y
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

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

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

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

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

        if x == y:
            return

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

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

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

uf = UnionFindWithRank(n)
uf = UnionFind(n)
bd = dict()
fd = dict()
directcount = [0] * n

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

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

res = [0] * n
ures = uf.all_group_members()
#print(ures)
for k in ures:
    cnt = len(ures[k]) - 1
    for node in ures[k]:
        res[node] = cnt - directcount[node]
for i in range(len(blist)):
    c, d = blist[i]
    if uf.same(c, d):
        res[c] -= 1
        res[d] -= 1
#print(directcount)
print(" ".join(list(map(str, res))))

Submission status: Time Limit Exceeded

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

#uf = [0]*N
#for i,ls in enumerate(c_comp):
#    for val in ls:
#        uf[int(val)-1] = i
for (a,b) in cd:
    if c_comp[a-1] == c_comp[b-1]:
        dic[str(a)].append(str(b))
        dic[str(b)].append(str(a))
res = [0]*N
"""
for ls in c_comp:
    leng = len(ls)-1
    for idx in ls:
        res[int(idx)-1] = leng - len(dic[idx])
"""
for i in range(N):
    res[i] = len_ls[c_comp[i]-1] - len(dic[str(i+1)])
print(*res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import connected_components
from scipy.sparse import lil_matrix
import collections

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

friend_mtx = lil_matrix((n, n))

friend_cnt = [0] * n
blocked_cnt = [0] * n

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

csr_mtx = friend_mtx.tocsr()
num, labels = connected_components(csr_mtx)

for i in range(k):
    c, d = map(int, input().split())
    if labels[c-1] == labels[d-1]:
        blocked_cnt[c-1] = blocked_cnt[c-1] + 1
        blocked_cnt[d-1] = blocked_cnt[d-1] + 1

renketsu_cnt = collections.Counter(labels)

for i in range(n):
    i_label = labels[i]
    renketsu_cnt_i = renketsu_cnt[i_label]
    num_friend = friend_cnt[i]
    num_blocked = blocked_cnt[i]
    print(renketsu_cnt_i - num_friend - num_blocked - 1, end="")
    if i != (n-1):
        print(' ', end="")
    else:
        print()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
N,M,K = map(int,input().split())
follow = [[False for i in range(N)] for j in range(N)]
block = [[False for i in range(N)] for j in range(N)]
edges = [0 for i in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    A = A-1
    B = B-1
    follow[A][B] = True
    follow[B][A] = True
    edges[A] = edges[A] + 1
    edges[B] = edges[B] + 1

n,labels = connected_components(np.array(follow))

groupV = [0]*n
for i in range(N):
    groupV[labels[i]] = groupV[labels[i]] + 1

for i in range(K):
    C,D = map(int,input().split())
    C = C-1
    D = D-1
    if (labels[C] != labels[D]) : continue
    block[C][D] = True
    block[D][C] = True
    edges[C] = edges[C] + 1
    edges[D] = edges[D] + 1

ans = ["0"]*N

for i in range(N):
    ans[i] = str(groupV[labels[i]] - 1 - edges[i])

print(" ".join(ans))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


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

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

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

        if x == y:
            return

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

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

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def resolve():
    n, m, k = map(int, input().split())
    u = UnionFind(n)
    d = defaultdict(lambda: [])
    e = defaultdict(lambda: [])
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        u.union(a, b)
        d[a].append(b)
        d[b].append(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        e[a].append(b)
        e[b].append(a)
    ans = [0] * n
    for i, v in u.all_group_members().items():
        for j in v:
            for k in v:
                if k != j and (not k in d[j]) and (not k in e[j]):
                    ans[k] += 1
    print(*ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

N, M , K = [int(x) for x in input().split()]
AB = []
G_F = [deque([]) for _ in range(N)]
G_B = [deque([]) for _ in range(N)]
G_F_s = [set() for _ in range(N)]
G_B_s = [set() for _ in range(N)]
for _ in range(M):
    AB = [int(x) for x in input().split()]
    G_F[AB[0] - 1].append(AB[1] - 1)
    G_F[AB[1] - 1].append(AB[0] - 1)
    G_F_s[AB[0] - 1].add(AB[1] - 1)
    G_F_s[AB[1] - 1].add(AB[0] - 1)

CD = []
for _ in range(K):
    CD = [int(x) for x in input().split()]

    G_B[CD[0] - 1].append(CD[1] - 1)
    G_B[CD[1] - 1].append(CD[0] - 1)
    G_B_s[CD[0] - 1].add(CD[1] - 1)
    G_B_s[CD[1] - 1].add(CD[0] - 1)

ans = 0
from collections import deque
G_F = deque(G_F)
G_B = deque(G_B)

# グラフの作成(無向グラフでは#を消す)

time = 0
arrive_time = [-1] * (N) # 到着時刻

# 深さ優先探索
def dfs(v, graph):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            stack.pop()          
    return arrive_time
import copy
ans = [0] * N
for i in range(N - 1):
    arrive_time = [-1] * N
    graph = copy.deepcopy(G_F)
    arrive_time = dfs(i, graph)
    for j in range(i + 1, N):
        if j in G_B_s[i] or j in G_F_s[i]:
            continue
        if arrive_time[j] > 0:
            ans[i] += 1
            ans[j] += 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,K = list(map(int,input().split(' ')))
friend = {}
bad = {}
friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

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

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

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



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    if A<B:
        friend[A*(10**5+1)+B]=1
    else:
        friend[A*(10**5+1)+B]=1
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

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



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

kouho = [0]*N

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

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

Submission status: Time Limit Exceeded

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

n,m,k = map(int, input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return set(i for i in range(self.n) if self.find(i) == root)

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n+1)
for a,b in ab:
    uf.union(a,b)


f_dict = {}
b_dict = {}
for i in range(1,n+1):
    f_dict[i] = []
    b_dict[i] = []

for a,b in ab:
    f_dict[a].append(b)
    f_dict[b].append(a)

for c,d in cd:
    if(uf.same(c,d)):
        b_dict[c].append(d)
        b_dict[d].append(c)

ans = [0] * (n+1)

for i in range(1,n+1):
    group = uf.members(i)
    for j in b_dict[i]:
        group.discard(j)
    ans[i] = len(group) - len(f_dict[i]) - 1

print(' '.join(map(str, ans[1:])))

Submission status: Time Limit Exceeded

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

n, m, k = list(map(int, input().split()))
ab_list = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list[a-1][b-1] = 1
    ab_list[b-1][a-1] = 1
# ab_list = [list(map(int, input().split())) for _ in range(m)]
cd_list = [[] for _ in range(n)]
for _ in range(k):
    c, d = list(map(int, input().split()))
    cd_list[c-1].append(d)
    cd_list[d-1].append(c)
# cd_list = [list(map(int, input().split())) for _ in range(k)]
csr = csr_matrix(ab_list)
shortest = shortest_path(csr, method='D')

# print(shortest)
# print(cd_list)

result = [0 for _ in range(n)]

for i in range(1, n+1):
    count = 0
    for j, ele in enumerate(shortest[i-1]):
        if i == j+1 or ele == np.inf or ele == 1:
            continue
        if j+1 not in cd_list[i-1]:
            count += 1
    result[i-1] = count

print(' '.join(str(ele) for ele in result))