Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        #親ノードの番号を格納
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
        self.group = [set([i]) for i in range(n)]
    def find(self, x):
        #根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self, x, y):
        #同じかどうかの確認
        return self.find(x) == self.find(y)
    def union(self, x, y):
        #統合する
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
            self.group[y] = self.group[x] | self.group[y]

        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            self.group[x] = self.group[x] | self.group[y]

        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            self.group[x] = self.group[x] | self.group[y]

    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
u = UnionFind(n+1)
li = []
ans_li = [-1 for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    ans_li[a] -= 1
    ans_li[b] -= 1
for i in range(k):
    a,b = map(int, input().split())
    li.append([a,b])
    p = u.find(a)
    s = u.group[p]
    if b in s:
        ans_li[a] -= 1
        ans_li[b] -= 1
index = 0
for i in range(1,n+1):
    p = u.find(i)
    ans_li[i] += len(u.group[p])
for i in range(1,n+1):
    print(ans_li[i], end = " ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

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

def union(uft, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return
    uft[x] = y

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        union(uft, a, b)
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        root(uft, i)
    for i in range(1, n+1):
        group[root(uft, i)].add(i)
    return ' '.join(str(len(group[uft[i]]-block[i])-len(friend[i])-1) for i in range(1, n+1))

print(answer())

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    AB = [tuple(map(int, ab)) for ab in map(str.split, args[1:1+m])]
    CD = [tuple(map(int, cd)) for cd in map(str.split, args[1+m:1+m+k])]

    friends = [set() for _ in range(n+1)]
    blocked = [set() for _ in range(n+1)]

    for a, b in AB:
        friends[a].add(b)
        friends[b].add(a)

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

    ret = [0]*(n+1)
    for a in range(1, n+1):
        checked = set((a,))
        stack = list(friends[a])
        while stack:
            b = stack.pop()
            if b in checked:
                continue

            checked.add(b)
            if b not in blocked[a] | friends[a]:
                ret[a] += 1

            stack.extend(friends[b]-checked)

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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

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

x= [[] for i in range(n)] # 友達関係のグラフ
y= [[] for i in range(n)] # ブロック関係のグラフ


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

for i in range(k):
    x[c[i][0]-1].append(c[i][1]-1)
    x[c[i][1]-1].append(c[i][0]-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())

uf=UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)

ans=[]
for i in range(n):
    ans.append(uf.size(i)-len(set(uf.members(i))&set(x[i]))-1)

print(*ans)

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(int)
    e = defaultdict(int)
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        u.union(a, b)
        d[a] += 1
        d[b] += 1
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        if u.same(a, b):
            e[a] += 1
            e[b] += 1
    ans = [0] * n
    for i, v in u.all_group_members().items():
        x = len(v) - 1
        for j in v:
            ans[j] = x-d[j] - e[j]
    print(*ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
from collections import defaultdict
setrecursionlimit(100001)
n, m, k = map(int, input().split())
ab = []
cd = []
for _ in range(m):
    ab.append(list(map(int, input().split())))
for _ in range(k):
    cd.append(list(map(int, input().split())))
friendsof = defaultdict(list)
for a, b in ab:
    friendsof[a - 1].append(b - 1)
    friendsof[b - 1].append(a - 1)
enemiesof = defaultdict(list)
for c, d in cd:
    enemiesof[c - 1].append(d - 1)
    enemiesof[d - 1].append(c - 1)
canfrinums = []
def dps(i, output):
    output.append(i)
    for fr in friendsof[i]:
        if fr not in output:
            dps(fr, output)
canfris = [None] * n
for i in range(n):
    if canfris[i] == None:
        canfri_i = []
        dps(i, canfri_i)
        lencan = 0
        for x in canfri_i:
            if x != i and x not in friendsof[i] and x not in enemiesof[i]:
                lencan += 1
        for j in canfri_i:
            canfris[j] = canfri_i
        canfrinums.append(lencan)
    else:
        canfri_i = canfris[i]
        canfrinums.append(len(set(canfri_i) - set(enemiesof[i])) - 1 - len(friendsof[i]))
print(' '.join(map(str, canfrinums)))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size)]
        self.rank = [0] * size
 
    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def is_same(self, x, y):  # check two vertices are in the same group
        return self.find(x) == self.find(y)
 
    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # the same group
            return
        # unite a small one to a bigger one to balance trees
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    N,M,K = map(int,input().split())
    fris = set()
    for _ in range(M):
        fris.add(tuple(sorted([int(i) -1 for i in input().split()])))
    blos = set()
    for _ in range(K):
        blos.add(tuple(sorted([int(i) -1 for i in input().split()])))
    uf = UnionFind(N)
    for a,b in fris:
        #if a == b-1 or b == a-1:
        uf.unite(a,b)
    alls = fris.union(blos)
    #print(alls)
    countl = []
    for i in range(N):
        count = 0
        for j in range(N):
            if i == j:
                #print(i,"==",j)
                continue
            if tuple(sorted([i, j])) in alls:
                #print(i,"fri or blo",j)
                continue
            #if i == j -1 or j == i-1:
            #    count += 1
            if uf.is_same(i,j):
                count += 1
            #else:
            #    print(i,"else",j)
        countl.append(str(count))
    print(" ".join(countl))

    #print("Yes") if uf.is_same(a, b) else print("No")
    
                

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group = [set() for _ in range(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)
        if not self.group[root]:
            for i in range(self.n):
                if self.find(i) == root:
                    self.group[root].add(i)
        return self.group[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, input().split())
    friends = [set() for _ in range(N)]
    block = [set() for _ in range(N)]
    uni = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        friends[A].add(B)
        friends[B].add(A)
        uni.union(A,B)
 
    for _ in range(K):
        C, D = map(int, input().split())
        C -= 1
        D -= 1
        block[C].add(D)
        block[D].add(C)
    
    tmp = [set() for _ in range(N)]
    ans = [0] * N
    for i in range(N):
        #ans[i] = len((uni.members(i) - friends[i]) - block[i]) - 1
        root = uni.find(i)
        tmp[root].add(i)

    for i in range(N):
        root = uni.find(i)
        ans[i] = len((tmp[root] - friends[i]) - block[i]) - 1
        
    print(*ans)
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
import numpy as np

n, m, k = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)

es2 = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    es2[c].append(d)
    es2[d].append(c)

ans = [0]*n

for i in range(n):
    visited = [False] * n
    i_good = es1[i]
    i_bad = es2[i]
    visited
    queue = deque()
    queue.extendleft(i_good)

    while len(queue):
        next_ = queue.pop()
        if visited[next_] == False:
            if (not next_ in i_good) and (not next_ in i_bad):
                ans[i] += 1
            visited[next_] = True
            queue.extendleft(es1[next_])

    ans[i] -= 1
    if ans[i] < 0:
        ans[i] = 0

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

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

  def find(self, x):
    if self.parents[x] == x:
      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.rank[x] < self.rank[y]:
      self.parents[x] = y
    else:
      self.parents[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1


if __name__ == '__main__':
  N, M, K = list(map(int, input().split()))
  uf = UnionFindByRank(N + 1)
  #A, B, C, D = [0] * M, [0] * M, [0] * K, [0] * K
  computed = set()
  for i in range(M):
    # friends
    #A[i], B[i] = list(map(int, input().split()))
    pair = tuple(sorted(map(int, input().split())))
    computed.add(pair)
    uf.union(pair[0], pair[1])
  for i in range(K):
    # blocks
    computed.add(tuple(sorted(map(int, input().split()))))

res = [0] * N

for i in range(1, N):
  cnt = 0
  for j in range(i + 1, N + 1):
    t = (min(i, j), max(i, j))
    if not t in computed and uf.find(i) == uf.find(j):
      cnt += 1
      res[j - 1] += 1
      computed.add(t)
  res[i - 1] += cnt

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

Submission status: Time Limit Exceeded

Solution code:
import copy

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

fl=[set() for i in range(n)]
for i in range(m):
    tmp_a,tmp_b=map(int,input().split())
    fl[tmp_a-1].add(tmp_b-1)
    fl[tmp_b-1].add(tmp_a-1)

bl=[set() for i in range(n)]
for i in range(k):
    tmp_a,tmp_b=map(int,input().split())
    bl[tmp_a-1].add(tmp_b-1)
    bl[tmp_b-1].add(tmp_a-1)
    
fp=[set() for i in range(n)]
start_set={i for i in range(n)}

for i in range(n):
    if len(fp[i])==0:
        tmp=i
        chain={i}
        search=[i]
        while len(search)>0:
            tmp=search.pop() 
            dif=fl[tmp].difference(chain)
            chain = chain.union(dif)
            search.extend(list(dif))
        for j in chain:
            fp[j]=copy.copy(chain)

for i in range(n):
    fp[i].discard(i)
    fp[i]=fp[i].difference(fl[i])
    fp[i]=fp[i].difference(bl[i])

al=list(map(len,fp))
print(' '.join(map(str,al)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

n, m, k = map(int, input().split())
AB = [map(int, input().split()) for _ in range(m)]
CD = [map(int, input().split()) for _ in range(k)]

graph_f = defaultdict(set)
graph_b = defaultdict(set)

for a, b in AB:
    graph_f[a].add(b)
    graph_f[b].add(a)

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

res = [0] * n

for i in range(1, n + 1):
    reachables = dfs(graph_f, i)
    for j in range(1, n + 1):
        if i == j:
            continue
        else:
            if j in reachables and j not in graph_f[i] and j not in graph_b[i]:
                res[i - 1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
import numpy as np

n, m, k = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)

es2 = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    es2[c].append(d)
    es2[d].append(c)

ans = [0]*n

@lru_cache(maxsize=None)
def calc(i):
    ans = 0
    visited = [False] * n
    i_good = np.array(es1[i])
    i_bad = np.array(es2[i])
    visited
    queue = deque()
    queue.extend(i_good)

    while len(queue):
        next_ = queue.pop()
        if visited[next_] == False:
            if (not next_ in i_good) and (not next_ in i_bad):
                ans += 1
            visited[next_] = True
            queue.extend(es1[next_])

    ans -= 1
    if ans < 0:
        ans = 0

    return ans



for i in range(n):
    ans[i] = calc(i)

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import collections

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

friends = collections.defaultdict(set)

for i in range(M):
    a, b = map(int, input().split())

    friends[a].add(b)
    friends[b].add(a)

exist_path = {}

def width_first(neighbor, start):
    visited = []
    queue = []
    queue.append(start)
    result = []
    while len(queue) > 0:
        next_city = queue.pop(0)
        if next_city in visited:
            continue
        result.append(next_city)
        visited.append(next_city)
        for nei in neighbor[next_city]:
            queue.append(nei)
    return result

blocks = collections.defaultdict(set)

for i in range(K):
    a, b = map(int, input().split())

    blocks[a].add(b)
    blocks[b].add(a)


import itertools

new_friends = collections.OrderedDict({i: 0 for i in range(1, N+1)})

for combi in itertools.combinations(range(1, N+1), 2):
    if combi[0] in friends[combi[1]] or combi[0] in blocks[combi[1]]:
        continue

    result = width_first(friends, combi[0])

    if combi[1] in result:
        new_friends[combi[0]] += 1
        new_friends[combi[1]] += 1

print(*new_friends.values())

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, frnd, blck = map(int, input().split())
    blst = [set() for i in range(n)]
    flst = [set() for i in range(n)]
    alst = [set() for i in range(n)]
    for _ in range(frnd):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        flst[a].add(b)
        flst[b].add(a)
        alst[a] = alst[a] | alst[b] | flst[a] | flst[b]
        alst[b] = alst[a] | alst[b] | flst[a] | flst[b]
        for v in alst[a]:
            alst[v] = alst[v] | alst[b]
    for _ in range(blck):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        blst[c].add(d)
        blst[d].add(c)
    for i in range(n):
        if i in alst[i]:
            alst[i].remove(i)
        for v in flst[i]:
            if v in alst[i]:
                alst[i].remove(v)
        for v in blst[i]:
            if v in alst[i]:
                alst[i].remove(v)
    for i in range(n):
        print(len(alst[i]), end="")
        if i < n:
            print(" ", end="")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int , input().split())
dif = set([i for i in range(1, n+1)])
m_list = [[] for _ in range(n+1)]
uni = [i for i in range(n+1)]
ab = sorted([list(map(int, input().split())) for _ in range(m)])
cd = [list(map(int, input().split())) for _ in range(k)]
for i in range(m):
    a, b = ab[i]
    m_list[a].append(b)
    m_list[b].append(a)
    a, b = sorted([a, b])
    for j in range(1, n+1):
        if uni[j] == uni[b]:
            uni[j] = uni[a]
    uni[b] = uni[a]

k_list = [[] for _ in range(n+1)]
for i in range(k):
    a, b = cd[i]
    k_list[a].append(b)
    k_list[b].append(a)


result = [0 for i in range(n+1)]
for i in range(1, n+1):
    r = dif - set(m_list[i])
    r = r - set(k_list[i])
    r = r - set([i])
    for j in list(r):
        if uni[j] == uni[i]:
            result[i] += 1

print(*result[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
# ブロック関係でないかつ同じグループ
class UnionFind():
    # nはノードの数
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n  # 根のノードは限らないので注意

    # xはノードの番号
    def find(self, x):  # あるノードの親を探すためのメソッド
        if self.parents[x] < 0:  # 親の場合、そのグラフの要素の個数を負の値で保持している
            return x
        else:
            # 再帰的に親を探しにいき、得られた値を格納する
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # x, yはノードの番号
    def union(self, x, y):
        x = self.find(x)  # 根の番号を取得
        y = self.find(y)  # 根の番号を取得
        if x == y:
            return  # 同じ親ならば合体させる必要はない

        # ※ それぞれ要素の個数が負の値で格納されている
        if self.parents[x] > self.parents[y]:
            # yのグループの方が要素の個数が多い場合 (yの方が値が小さいということは、負の世界では値が大きいため)
            # 必ずxの方が要素が多い状態にする
            x, y = y, x

        self.parents[x] += self.parents[y]  # 負の値同士だが、これで良い
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    # xはノードの番号
    def size(self, x):
        # 親まで辿ればグループの大きさが負の値で格納されているため、それにマイナスをつけてreturnする
        return -self.parents[self.find(x)]

    # x, yはノードの番号
    def same(self, x, y):
        # 親が同じ = 同じグループに属するならTrueがreturnされる
        return self.find(x) == self.find(y)

    # xはノードの番号
    def members(self, x):
        root = self.find(x)  # 親の値を取得する
        # findで再帰的に親の値が獲得できる
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        # 親となっているノードの番号をリストでreturnする
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_counts(self):
        # グループの数をreturnする
        return len(self.roots())

    def all_group_members(self):
        # 親のノードの番号をキーにして、子のノードの番号を対応させた辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        # printした時の表記
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())  # N人の人, M人の友好関係, K個のブロック関係
uf = UnionFind(N)

# inはsetを使ってオーダー1
addjacent = defaultdict(set)
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    addjacent[a].add(b)
    addjacent[b].add(a)
    uf.union(a, b)
blocked = defaultdict(set)
for _ in range(K):
    c, d = map(lambda x: int(x)-1, input().split())
    blocked[c].add(d)
    blocked[d].add(c)

# # 親の数だけ行う
pearents = uf.all_group_members()
# # print(pearents)
# ans = defaultdict(int)
# for group in pearents.values():
#     for n in group:
#         ans[n] = len(group) - 1 - len(addjacent[n]) - len(set(group)&blocked[n])
#     # groupの中にブロックがいるかどうか
#
# ans = " ".join(map(str, ans.values()))
# print(ans)

for i in range(N):
    print(uf.size(i) - len(addjacent[i]) - len(blocked[i]&set(uf.members(i))) - 1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def solve(inp):
    (N, M, K) = map(int, inp.readline().strip().split(' '))
    AB = [map(int, inp.readline().strip().split(' ')) for i in range(M)]
    CD = [map(int, inp.readline().strip().split(' ')) for i in range(K)]

    A2B = [set() for i in range(N + 1)]
    for a, b in AB:
        A2B[a].add(b)
        A2B[b].add(a)
    C2D = [set() for i in range(N + 1)]
    for c, d in CD:
        C2D[c].add(d)
        C2D[d].add(c)

    # print('A2B=' + str(A2B))
    # print('C2D=' + str(C2D))

    cl = [x.copy() for x in A2B]
    i = 1
    while i <= N:
        js = cl[i].copy()
        for j in js:
            for k in cl[j]:
                if k != i:
                    cl[i].add(k)
            cl[j] = set()
        if len(js) == len(cl[i]):
            i += 1  # next

    r = [0 for i in range(N + 1)]
    for i in range(1, N + 1):
        l = len(cl[i])
        if len(cl[i]) > 0:
            r[i] = l
            for j in cl[i]:
                r[j] = l
                cl[j] = cl[i].copy()
                cl[j].remove(j)
                cl[j].add(i)

    for i in range(1, N + 1):
        r[i] -= len(A2B[i])

    for i in range(1, N + 1):
        for j in C2D[i]:
            if j in cl[i]:
                r[i] -= 1

    r.remove(0)
    return " ".join(map(str, r))


def main():
    import sys
    result = solve(sys.stdin)
    if result is not None and result != '':
        print(result)


if __name__ == '__main__':
    main()

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(N+1)]
    for i in range(M):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        join(ai, bi)
        mk[ai].add(bi)
    for i in range(K):
        ai, bi = iim()
        if ai > bi:
            ai, bi = bi, ai
        mk[ai].add(bi)

    ans = [0] * (N+1)
    #print(S)
    S1 = [[] for i in range(N+1)]
    for i in range(1, N+1):
        ai = find(i)
        S1[ai].append(i)

    for ss in S1:
        ls = len(ss)
        for i in range(ls-1):
            ai = ss[i]
            mki = mk[ai]
            for j in range(i+1, ls):
                aj = ss[j]
                if aj in mki:
                    continue
                if same(ai, aj):
                    ans[ai] += 1
                    ans[aj] += 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
a3 = [[] for i in range(n)]
for i in range(n):
  j = a2[i]
  while j != a2[j]:
    j = a2[j]
  a2[i] = j
  a3[j].append(i)
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 = [0]*n
for i in range(n):
  f[i] += len(set(a3[a2[i]]) - set(a[i]+c[i]+[i]))
print(" ".join([str(i) for i in f]))