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:
#!/usr/bin/env python3
import sys
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 tup(a,b):
    return (min(a,b),max(a,b))

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    friends = defaultdict(bool)
    group = UnionFind(N)
    for i in range(M):
        friends[tup(A[i]-1,B[i]-1)] = True
        group.union(A[i]-1,B[i]-1)
    for i in range(K):
        friends[tup(C[i]-1,D[i]-1)] = True
    result = ""
    isFirst = True
    roots = group.roots()
    rootSets = {r: set() for r in roots }
    for i in range(N):
        r = group.find(i)
        rootSets[r].add(i)
    for i in range(N):
        c = 0
        r = group.find(i)
        for g in rootSets[r]:
            if g != i and not friends[tup(i,g)]:
                c+= 1
        if not isFirst:
            result+=" "
        else:
            isFirst = False
        result+=str(c)
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

class UnionFind(object):
    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 main():
    n, m, k = map(int, raw_input().split())
    uf = UnionFind(n)
    ff = {}
    block = {}
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        ff.setdefault(a, set()).add(b)
        ff.setdefault(b, set()).add(a)
        uf.union(a, b)
    for _ in xrange(k):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        block.setdefault(a, set()).add(b)
        block.setdefault(b, set()).add(a)

    clusters = uf.all_group_members().values()
    ans = [0] * n
    for cluster in clusters:
        for i in cluster:
            size = len(cluster - {i} - block.get(i, set()) - ff.get(i, set()))
            ans[i] = size
    print ' '.join(map(str, ans))

main()

Submission status: Time Limit Exceeded

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

uf = UnionFind(N)

friend = [[False]*N for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    friend[a][b] = True
    friend[b][a] = True

block = [[False]*N for _ in range(N)]

for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    block[c][d] = True
    block[d][c] = True

res = [0]*N

gp = list(uf.all_group_members().values())

for g in gp:
    for i in range(len(g)):
        for j in range(i+1, len(g)):
            n = g[i]
            m = g[j]
            if friend[n][m] or block[n][m]:
                continue
            else:
                res[n] += 1
                res[m] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


def main():
    N, M, K = [int(x) for x in input().split()]

    uf = UnionFind(N)
    fcount = defaultdict(int)
    for _ in range(M):
        A, B = [int(x) for x in input().split()]
        uf.union(A-1, B-1)
        fcount[A-1]+=1
        fcount[B-1]+=1

    import collections
    blocks = collections.defaultdict(set)
    for _ in range(K):
        C, D = [int(x) for x in input().split()]
        blocks[C-1].add(D-1)
        blocks[D-1].add(C-1)

    groups = collections.defaultdict(set)
    for i in range(N):
        groups[uf.find(i)].add(i)

    counts = []
    for i in range(N):
        friends = groups[uf.find(i)]
        cnt = len(friends)-1-fcount[i]-len([f for f in friends if f in blocks[i]])
        counts.append(cnt)
    print(" ".join(map(str, counts)))


if __name__ == '__main__':
    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 = list(map(int, input().split()))
uf = UnionFind(N[0])
friends = {i:[] for i in range(N[0])}
for i in range(N[1]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  friends[x].append(y)
  friends[y].append(x)  
  uf.union(x, y)
blocks = {i:[] for i in range(N[0])}
for i in range(N[2]):
  x, y = list(map(int, input().split()))
  x, y = x - 1, y - 1
  blocks[x].append(y)
  blocks[y].append(x)  

results = []
for i in range(N[0]):
  results.append(str(len(set(uf.members(i)) - set(friends[i]) - set(blocks[i])) - 1))
print(" ".join(results))

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

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):
    for j in range(i + 1, N):
        arrive_time = [-1] * N
        if j in G_B[i] or j in G_F[i]:
            continue
        graph = copy.deepcopy(G_F)
        arrive_time = dfs(i, graph)
        if arrive_time[j] > 0:
            ans[i] += 1
            ans[j] += 1

print(*ans)

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.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  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):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[y] = x
    else:
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x):
    return -self.root[self.Find_Root(x)]

ans = []
uf = UnionFind(n+1)
for a, b in ab:
  uf.Unite(a, b)

adlist = [set() for i in range(n+1)]
for a, b in ab:
  adlist[a].add(b)
  adlist[b].add(a)
for i in range(1, n+1):
  adlist[i].add(i)
for c, d in cd:
  adlist[c].add(d)
  adlist[d].add(c)

tmp = set([i for i in range(1, n+1)])

for i in range(1, n+1):
  adlist[i] = tmp - adlist[i] 


for i in range(1, n+1):
  if len(adlist[i]) != 0:
    a = 0 
    for j in adlist[i]:
      if uf.isSameGroup(i, j):
        a += 1 

    ans += [a]
  else:
    ans += [0]

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

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 [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:
    b_dict[c].append(d)
    b_dict[d].append(c)

ans = [0] * (n+1)

for i in range(1,n+1):
    group = set(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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

    def root(self, x):
        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g

@mt
def slv(N, M, K, AB, CD):
    ans = 0
    f = UnionFind()
    block = defaultdict(set)
    direct = defaultdict(set)
    for a, b in AB:
        f.union(a, b)
        direct[a].add(b)
        direct[b].add(a)

    done = set()
    a = set(range(1, N+1))
    while len(done) != N:
        u = list(a - done)[0]
        done.add(u)
        for i in a:
            if f.same(u, i):
                done.add(i)

    g = defaultdict(set)
    for i in range(1, N+1):
        x = f.root(i)
        g[x].add(i)

    for c, d in CD:
        block[c].add(d)
        block[d].add(c)

    ans = []
    for i in range(1, N+1):
        cand = g[f.root(i)] - set([i])
        cand = cand - block[i]
        cand = cand - direct[i]
        ans.append(len(cand))
    return ans


def main():
    N, M, K = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    CD = [read_int_n() for _ in range(K)]
    print(*slv(N, M, K, AB, CD))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
connect = [[] for _ in range(n)]
cCnt = [0 for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    connect[a - 1].append(b - 1)
    cCnt[a - 1] += 1
    connect[b - 1].append(a - 1)
    cCnt[b - 1] += 1

group = [0 for _ in range(n)]
gNum = 0
import queue
for i in range(n):
    if group[i]:
        continue
    gNum += 1
    next = queue.Queue()
    for j in connect[i]:
        next.put(j)
    group[i] = gNum

    while not next.empty():
        j = next.get()
        group[j] = gNum
        for l in connect[j]:
            if not group[l]:
                next.put(l)

hunaka = [0 for i in range(n)]
for i in range(k):
    c, d = map(int, input().split())
    if group[c - 1] != group[d - 1]:
        continue
    hunaka[c - 1] += 1
    hunaka[d - 1] += 1

groupCnt = [0 for _ in range(gNum + 1)]
for i in group:
    groupCnt[i] += 1

for i in range(n):
    tmp = groupCnt[group[i]]
    tmp -= cCnt[i]
    tmp -= hunaka[i]
    tmp -= 1
    print(tmp, end = " ")

Submission status: Time Limit Exceeded

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

class UnionFind(object):
    def __init__(self, N):
        # 初期状態を定義。ルートは -1から始まり、-X と負数でグループのサイズをもつ
        self.node = [-1] * N

    def root(self, x):
        if self.node[x] < 0:
            # それ自身がrootなら自分のポジションを返却
            return x
        else:
            # ルートを再帰で辿って、それぞれルートに直つなぎにする
            self.node[x] = self.root(self.node[x])
            # 自分がつながってるルートのポジションを返却
            return self.node[x]

    def size(self, x):
        # xが所属するグループのサイズを取得
        # サイズは負の数で管理されてるので、-1倍して返却
        return -self.node[self.root(x)]

    def connect(self, x, y):
        a = self.root(x)  # x のrootの位置
        b = self.root(y)  # y のrootの位置

        # もう同じグループなら何もしない
        if a == b:
            return

        # サイズが大きい方をaとして取り回す
        if self.size(a) < self.size(b):
            a, b = b, a

        # aのサイズをbのサイズを含む形に更新する（負数同士の足し算）
        self.node[a] += self.node[b]
        # bをaに連結する
        self.node[b] = a

        return

    def show_nodes(self):
        return self.node


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

    tree = UnionFind(N)
    friends = [[False] * N for _ in range(N)]
    block = [[False] * N for _ in range(N)]

    for _ in range(M):
        A, B = map(int,input().split())
        tree.connect(A-1, B-1)
        friends[A-1][B-1] = True
        friends[B-1][A-1] = True

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

    # print(friends)
    # print(block)
    # print(tree.show_nodes())

    # per person
    ans = [0] * N
    for i in range(N):
        maybe_friend = 0
        for j in range(N):
            if i == j:
                continue

            # already firend?
            if friends[i][j]:
                continue
            # not blocK?
            if block[i][j]:
                continue

            if tree.root(i) == tree.root(j):
                maybe_friend += 1

        ans[i] = maybe_friend

    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def connected_components(graph):
  seen = set()
  def component(n):
    nodes = set([n])
    while nodes:
      n = nodes.pop()
      seen.add(n)
      nodes |= set(graph[n]) - seen
      yield n
  for n in graph:
    if n not in seen:
      yield component(n)

n,m,k=map(int,input().split())
friend={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  friend[a-1].add(b-1)
  friend[b-1].add(a-1)
block={i:set() for i in range(n)}
for i in range(k):
  c,d=map(int,input().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)
checked=set()
belongs=[-1 for i in range(n)]
renketsu=[]
b = 0
g = [list(x) for x in connected_components(friend)]
fnum=[-1 for i in range(n)]
for graph in g:
  s = set(graph)
  for x in graph:
    fnum[x] = len(s - friend[x] - block[x]) - 1
print(' '.join(map(str,fnum)))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.tree = range(n)
        self.rank = [0] * n
    
    def root(self, n):
        if self.tree[n] == n:
            return n
        self.tree[n] = self.root(self.tree[n])
        return self.tree[n]

    def merge(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        if self.rank[a] > self.rank[b]:
            self.tree[b] = a
        elif self.rank[a] < self.rank[b]:
            self.tree[a] = b
        else:
            self.tree[a] = b
            self.rank[b] += 1

    def clusters(self):
        c = {}
        for i in xrange(self.n):
            j = self.root(i)
            c.setdefault(j, set()).add(i)
        return c.values()


def main():
    n, m, k = map(int, raw_input().split())
    uf = UnionFind(n)
    ff = {}
    block = {}
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        ff.setdefault(a, set()).add(b)
        ff.setdefault(b, set()).add(a)
        uf.merge(a, b)
    for _ in xrange(k):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        block.setdefault(a, set()).add(b)
        block.setdefault(b, set()).add(a)

    clusters = uf.clusters()
    ans = [0] * n
    for cluster in clusters:
        for i in cluster:
            size = len(cluster - {i} - block.get(i, set()) - ff.get(i, set()))
            ans[i] = size
    print ' '.join(map(str, ans))

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
import bisect
from math import factorial

def update_cluster(cluster, cluster_index, a, b):
    remain_index = cluster[a]
    delete_index = cluster[b]
    if remain_index == delete_index:
        return

    if len(cluster_index[remain_index]) < len(cluster_index[delete_index]):
        remain_index, delete_index = delete_index, remain_index

    movers = cluster_index[delete_index]
    for mover in movers:
        cluster[mover] = remain_index
        cluster_index[remain_index].add(mover)

    del cluster_index[delete_index]

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

    cluster = {i+1: i+1 for i in range(N)}
    cluster_index = {i+1: set([i+1]) for i in range(N)}
    blocks = defaultdict(set)

    for _ in range(M):
        a, b = map(int, input().split())
        update_cluster(cluster, cluster_index, a, b)
        blocks[a].add(b)
        blocks[b].add(a)

    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends = []
    for p, index in cluster.items():
        candidates = cluster_index[index]
        num = len(candidates - blocks[p]) - 1
        friends.append(str(num))

    print(" ".join(friends))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
inf = float('inf')
e = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    e[a][b] = 1
    e[b][a] = 1


from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
G = csgraph_from_dense(e, null_value=inf)
D = floyd_warshall(G)

# b = [[-1] * N for _ in range(N)]
for _ in range(K):
    c, d = map(int,input().split())
    c -= 1
    d -= 1
    D[c][d] = inf
    D[d][c] = inf


# print(D)
ans = []
for i in range(N):
    a = 0
    for j in range(N):
        if D[i][j] != inf and D[i][j] > 1:
            a += 1
    ans.append(a)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M, K = map(int, input().split())

Friend = [tuple(map(int, input().split())) for i in range(M)]
Block = [tuple(map(int, input().split())) for i in range(K)]

# 人iの友達関係リスト
set_Friend = [set() for i in range(N)]
for (A,B) in Friend:
  set_Friend[A-1].add(B-1)
  set_Friend[B-1].add(A-1)

# 人iのブロック関係リスト
set_Block = [set() for i in range(N)]
for (C,D) in Block:
  set_Block[C-1].add(D-1)
  set_Block[D-1].add(C-1)

# 友達関係による連結成分
cluster_id = 0
clusters = []
clustering = [-1 for i in range(N)]
for i in range(N):
  if clustering[i]!=-1:
    continue
  cluster_prev = set([i])
  cluster_diff = set([i])
  while len(cluster_diff)>0:
    cluster_next = set()
    for j in cluster_diff:
      cluster_next = cluster_next | set_Friend[j]
    cluster_diff = cluster_next - cluster_prev
    cluster_prev = cluster_next | cluster_prev
  for k in cluster_prev:
    clustering[k] = cluster_id
  clusters.append(cluster_prev)
  cluster_id += 1

# 友達候補の人数を計算して出力
for i in range(N):
  id = clustering[i]
  cluster = clusters[id]
  print(len(cluster-set_Friend[i]-set_Block[i]-set([i])), end='')
  if i<N:
    print(' ', end='')

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
relation = [[0]*(n+1) for i in range(n+1)]
rinsetu = {i:[] for i in range(1,n+1)}
for i in range(n):
  relation[i+1][i+1] = 1
for i in range(m):
    a, b = map(int, input().split())
    relation[a][b] = 1
    relation[b][a] = 1
    rinsetu[a].append(b)
    rinsetu[b].append(a)
for i in range(k):
    a, b = map(int, input().split())
    relation[a][b] = 1
    relation[b][a] = 1

def dfs(v):
    kouho.add(v)
    for nxt in rinsetu[v]:
        if nxt in kouho:
            continue
        dfs(nxt)

for i in range(1,n+1):
    kouho = set()
    s = 0
    dfs(i)
    for k in kouho:
      if(relation[i][k] == 0):
        s += 1
    print(s,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):
        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())

u = UnionFind(n)

frends = [set() for i in range(n)]

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

hate = [set() for i in range(n)]

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

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

for i in range(n):
    x = set(u.members(i))
    ans[i] = len(x - hate[i] - frends[i]) - 1


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