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
import copy
sys.setrecursionlimit(10**7)
n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
G=[[]for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

def dfs(now):
    global group
    for next in friend[now]:
        tansaku.append(next)
    while tansaku:
        next=tansaku.pop()
        visited[next]=True
        group.append(next)
        for k in friend[next]:
            if visited[k]==True:
                continue 
            if k in tansaku:
                continue
            tansaku.append(k)
   
    """
    for next in friend[now]:
        if visited[next]==False:
            visited[next]=True
            group.append(next)
            dfs(next)
     """       
    return group
group=[]
tansaku=[]
visited=[False]*n
for i in range(n):
    if visited[i]==False:
        visited[i]=True
        g=set(dfs(i))|{i}
        

        for x in g:
            G[x]=list(g-{x})
        group=[]
for i in range(n):
    ans=set(G[i])-set(friend[i])-set(block[i])
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import queue
import time
q = queue.Queue()

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

friend = [[] 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)

block = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)
    
group = []
group_num = [-1] * n
gn = 0
#t1 = time.time()
n_list = [l for l in range(n)]
while len(n_list):
    i = n_list[0]
    del n_list[0]
    if group_num[i] != -1:
        continue
    seen = [i]
    group_num[i] = gn
    q.put(i)
    while q.qsize() != 0:
        x = q.get()
        for j in friend[x]:
            if not j in seen:
                q.put(j)
                seen.append(j)
                group_num[j] = gn
                del n_list[n_list.index(j)]
    gn += 1
    group.append(seen)
    
#t2 = time.time()
#print(t2-t1)

#t3 = time.time()
c_list = []
for i in range(n):
    count = len(group[group_num[i]]) - len(set(group[group_num[i]]) & set(friend[i] + block[i])) - 1
    c_list.append(count)
#t4 = time.time()
#print(t4-t3)

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

Submission status: Time Limit Exceeded

Solution code:
import queue
q = queue.Queue()

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

friend = [[] 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)

block = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)
    
seen_list = []
group = []
group_num = [-1] * n
gn = 0
for i in range(n):
    if i in seen_list:
        continue
    seen = [i]
    group_num[i] = gn
    q.put(i)
    while q.qsize() != 0:
        x = q.get()
        for j in friend[x]:
            if not j in seen:
                q.put(j)
                seen.append(j)
                group_num[j] = gn
    gn += 1
    group.append(seen)
    seen_list += seen

#print(seen_list)
#print(group)
#print(group_num)

c_list = []
for i in range(n):
    count = len(group[group_num[i]]) - len(set(group[group_num[i]]) & set(friend[i] + block[i])) - 1
    c_list.append(count)

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
    us = [[i] for i in range(0,n+1)]
    for i in range(1, n + 1):
        for fr in fs[i]:
            if not us[i] is us[fr]:
                if len(us[i])>len(us[fr]):
                    us[i].extend(us[fr])
                    for aa in us[fr]:
                        us[aa] = us[i]
                else:
                    us[fr].extend(us[i])
                    for aa in us[i]:
                        us[aa] = us[fr]
    for i in range(1, n + 1):
        frens = len(us[i]) - 1 - len(fs[i])
        for blo in bs[i]:
            if blo in us[i]:
                frens -= 1
        print(frens, end=" ")
    print()
    return


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

fs = [[] for i in range(n + 1)]
bs = [[] for i in range(n + 1)]

for i in range(m):
    a, b = [int(s) for s in input().split(" ")]
    fs[a].append(b)
    fs[b].append(a)
for i in range(k):
    c, d = [int(s) for s in input().split(" ")]
    bs[c].append(d)
    bs[d].append(c)
solve()

Submission status: Time Limit Exceeded

Solution code:




def solve():
    us = [[i] for i in range(0,n+1)]
    for i in range(1, n + 1):
        for fr in fs[i]:
            if not us[i] is us[fr]:
                us[i].extend(us[fr])
                for aa in us[fr]:
                    us[aa] = us[i]
    # for i in len(us):
    #     us[i] = list(set(us[i]))
    for i in range(1, n + 1):
        frens = len(us[i]) - 1 - len(fs[i])
        for blo in bs[i]:
            if blo in us[i]:
                frens -= 1
        print(frens, end=" ")
    print()
    return


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

fs = [[] for i in range(n + 1)]
bs = [[] for i in range(n + 1)]

for i in range(m):
    a, b = [int(s) for s in input().split(" ")]
    fs[a].append(b)
    fs[b].append(a)
for i in range(k):
    c, d = [int(s) for s in input().split(" ")]
    bs[c].append(d)
    bs[d].append(c)
solve()

Submission status: Time Limit Exceeded

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

class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for i in range(n)]

    def find(self,x):
        if(self.parent[x]==x):
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):
            pass
        elif(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 same(self,x,y):
        return self.find(x)==self.find(y)

uf=UnionFind(n)
friendlist=[set() for _ in range(n)]
blocklist=[set() for _ in range(n)]


for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friendlist[a].add(b)
    friendlist[b].add(a)
    uf.unite(a,b)

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

grouplist={}
rootlist=[]
for i in range(n):
    rooti=uf.find(i)
    rootlist.append(rooti)
    groupi=grouplist.get(rooti, set())
    groupi.add(i)
    grouplist[rooti]=groupi

ans=[]
for i in range(n):
    ans.append(len(grouplist[rootlist[i]] - friendlist[i] - blocklist[i] ) - 1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.size = [1]*n

    def find(self,a):
        if self.parent[a] == a:
            return a
        else:
            return self.find(self.parent[a])

    def unite(self,a,b):
        a_parent = self.find(a)
        b_parent = self.find(b)
        if a_parent == b_parent:
            return
        else:
            if self.size_of(b_parent) > self.size_of(a_parent): 
                self.parent[a_parent] = self.parent[b_parent]
                self.size[b_parent] += self.size[a_parent]
            else:
                self.parent[b_parent] = self.parent[a_parent]
                self.size[a_parent] += self.size[b_parent]
                
    def size_of(self,a):
        return self.size[self.find(a)]
    
    def is_same(self,a,b):
        return self.parent(a) == self.parent(b)


N,M,K = map(int, input().split())
uf = UnionFind(N+1)
friends = []
blocks = []
for i in range(N+1):
    blocks.append([])
    friends.append(0)

for i in range(M):
    a,b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.unite(a,b)
    
for j in range(K):
    x,y = map(int, input().split())
    blocks[x].append(y)
    blocks[y].append(x)

for i in range(1,N+1):
    print(uf.size_of(i) - friends[i] - len([x for x in range(1,N+1) if i in blocks[x] and uf.find(i) == uf.find(x)])-1)

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
lt = [0]*N
lb = [0]*N
ln = [i for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -=1
    b -=1
    lt[a] += 1
    lt[b] += 1
    if ln[a]!= ln[b]:
        #print(ln[a],ln[b])
        ln = [ln[a] if j == ln[b] else j for j in ln]
        #print(ln)
for i in range(K):
    c,d = map(int,input().split())
    if ln[c-1] == ln[d-1]:
        lb[c-1] +=1
        lb[d-1] +=1
for i in range(N):
    print(ln.count(ln[i])-lt[i]-lb[i]-1,end = " ")
#print(lt,lb,ln)

Submission status: Time Limit Exceeded

Solution code:
import queue
import itertools
q = queue.Queue()

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

friend = [[] 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)

block = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)
    
seen_list = []
group = []
group_num = [-1] * n
gn = 0
for i in range(n):
    if i in seen_list:
        continue
    seen = [i]
    group_num[i] = gn
    q.put(i)
    while q.qsize() != 0:
        x = q.get()
        for j in friend[x]:
            if not j in seen:
                q.put(j)
                seen.append(j)
                group_num[j] = gn
    gn += 1
    group.append(seen)
    seen_list += seen

#print(seen_list)
#print(group)
#print(group_num)

c_list = []
for i in range(n):
    count = 0
    for j in group[group_num[i]]:
        if not j in friend[i] and not j in block[i]:
            count += 1
    c_list.append(count-1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
sys.setrecursionlimit(10**7)
n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
G=[[]for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

def dfs(now):
    global group
    for next in friend[now]:
        if visited[next]==False:
            visited[next]=True
            group.append(next)
            dfs(next)
            
    return group
group=[]
visited=[False]*n
for i in range(n):
    if visited[i]==False:
        visited[i]=True
        g=set(dfs(i))|{i}
        

        for x in g:
            G[x]=list(g-{x})
        group=[]
for i in range(n):
    ans=set(G[i])-set(friend[i])-set(block[i])
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m,k=map(int,input().split())
friend=[[]for i in range(n)]
block=[[]for i in range(n)]
G=[]

for i in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

def dfs(now):
    global group
    for next in friend[now]:
        if visited[next]==False:
            visited[next]=True
            group.append(next)
            dfs(next)
            
    return group
group=[]
visited=[False]*n
for i in range(n):
        visited=[False]*(n)
        visited[i]=True
        G.append(dfs(i))
        group=[]
for i in range(n):
    ans=set(G[i])-set(friend[i])-set(block[i])
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


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

union_find = UnionFind(n)
num_friends = [0]*(n+1)
num_block = [0]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    num_friends[a] += 1
    num_friends[b] += 1
    union_find.union(a, b)
# cd = [[_c, _d] for (_c, _d) in map(int, input().split())]
for i in range(k):
    # c[i], d[i] = map(int, input().split())
    c, d = map(int, input().split())
    if union_find.same_check(c, d):
        num_block[c] += 1
        num_block[d] += 1


num_suggest_friend = [-1]*(n+1)  # 自分自身を引いておくので-1で初期化
for i in range(1, n+1):
    for j in range(1, n+1):
        if (union_find.same_check(i, j)):
            num_suggest_friend[i] += 1
# print(*num_suggest_friend[1:], sep=' ')


for i in range(1, n+1):
    num_suggest_friend[i] = num_suggest_friend[i] - \
        num_friends[i] - num_block[i]
# print(*num_suggest_friend[1:], sep=' ')
# for c_, d_ in zip(c, d):
#     if union_find.same_check(c_, d_):
#         num_suggest_friend[c_] -= 1
#         num_suggest_friend[d_] -= 1

print(*num_suggest_friend[1:], sep=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


n, m, k = list(map(int, input().split()))
a = [0]*(m+1)
b = [0]*(m+1)
c = [0]*(k+1)
d = [0]*(k+1)
union_find = UnionFind(n)
num_friends = [0]*(n+1)
num_block = [0]*(n+1)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    num_friends[a[i]] += 1
    num_friends[b[i]] += 1
    union_find.union(a[i], b[i])
# cd = [[_c, _d] for (_c, _d) in map(int, input().split())]
for i in range(k):
    # c[i], d[i] = map(int, input().split())
    c, d = map(int, input().split())
    if union_find.same_check(c, d):
        num_block[c] += 1
        num_block[d] += 1

# frinds_mat = np.zeros([n, n])
# for i in range(m):
#     # a[i]とb[i]は友達
#     frinds_mat[a[i]-1, b[i]-1] = 1
#     frinds_mat[b[i]-1, a[i]-1] = 1
num_suggest_friend = [-1]*(n+1)  # 自分自身を引いておくので-1で初期化
for i in range(1, n+1):
    for j in range(1, n+1):
        if (union_find.same_check(i, j)):
            num_suggest_friend[i] += 1
# print(*num_suggest_friend[1:], sep=' ')


for i in range(1, n+1):
    num_suggest_friend[i] = num_suggest_friend[i] - \
        num_friends[i] - num_block[i]
# print(*num_suggest_friend[1:], sep=' ')
# for c_, d_ in zip(c, d):
#     if union_find.same_check(c_, d_):
#         num_suggest_friend[c_] -= 1
#         num_suggest_friend[d_] -= 1

print(*num_suggest_friend[1:], sep=' ')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np


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

    # 検索
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


n, m, k = list(map(int, input().split()))
a = [0]*(m+1)
b = [0]*(m+1)
c = [0]*(k+1)
d = [0]*(k+1)
union_find = UnionFind(n)
num_friends = [0]*(n+1)
for i in range(m):
    a[i], b[i] = map(int, input().split())
    num_friends[a[i]] += 1
    num_friends[b[i]] += 1
    union_find.union(a[i], b[i])
for i in range(k):
    c[i], d[i] = map(int, input().split())

# frinds_mat = np.zeros([n, n])
# for i in range(m):
#     # a[i]とb[i]は友達
#     frinds_mat[a[i]-1, b[i]-1] = 1
#     frinds_mat[b[i]-1, a[i]-1] = 1
num_suggest_friend = [-1]*(n+1)  # 自分自身を引いておくので-1で初期化
for i in range(1, n+1):
    for j in range(1, n+1):
        if (union_find.same_check(i, j)):
            num_suggest_friend[i] += 1
# print(*num_suggest_friend[1:], sep=' ')


for i in range(1, n+1):
    num_suggest_friend[i] -= num_friends[i]
# print(*num_suggest_friend[1:], sep=' ')
for c_, d_ in zip(c, d):
    if union_find.same_check(c_, d_):
        num_suggest_friend[c_] -= 1
        num_suggest_friend[d_] -= 1

print(*num_suggest_friend[1:], sep=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def dfs(friend, group, number, s):
    d = deque([s])
    
    while d:
        num = d.pop()
        if group[num] != 0:
            continue
        
        group[num] = number
        
        for n in friend[num]:
            d.append(n)
    
    return group
    
def main():
    n, m, k = map(int, input().split())
    
    friend = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        friend[a].append(b)
        friend[b].append(a)
    
    block = [[] for _ in range(n)]
    for _ in range(k):
        a, b = map(lambda x: int(x) - 1, input().split())
        block[a].append(b)
        block[b].append(a)
    
    group = [0] * n
    number = 1
    for i in range(n):
        if group[i] != 0:
            continue
        
        group = dfs(friend, group, number, i)
        number += 1
    
    link = []
    for i in range(number + 1):
        link.append(group.count(i))
        
    for i in range(n):
        if group[i] == 0:
            print(0, end=' ')
            continue
        ans = 0
        ans += link[group[i]]
        ans -= len(friend[i])
        for b in block[i]:
            if group[i] == group[b]:
                ans -= 1
        print(ans - 1, end=' ')
        
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, M, K = map(int, input().split())

# 友達関係をUFで用意
uf = UnionFind(N)

# 直接の友達のリスト
friend = [[]for i in range(N)]
# 直接のブロックのリスト
block = [[] for i in range(N)]

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

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

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

# 友達関係のグループの要素数ーグループ内の直接の友達の数ーグループ内の直接のブロックの数ー自分自身
for i in range(N):
    X = set(uf.members(i))
    Y = set(friend[i])
    Z = set(block[i])
    ans[i] = len(X) - len(X & Y) - len(X & Z) - 1

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

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
n, m, k = map(int, input().split())
uf = UnionFind(n)
E = [[] for i in range(n)]
E_d = [[] for i in range(n)]

import sys
input = sys.stdin.readline

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

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

num_men = [0]*n
for i in range(n):
  num_men[i] = uf.size(i) - 1
  for dn in E_d[i]:
    if uf.same(i, dn):
      num_men[i] -= 1
  num_men[i] -= len(E[i])
      
print(*num_men)

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())
uf = UnionFind(n)
E = [[] for i in range(n)]
E_d = [[] for i in range(n)]

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

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

num_men = [0]*n
for i in range(n):
  num_men[i] = uf.size(i) - 1
  for dn in E_d[i]:
    if uf.same(i, dn):
      num_men[i] -= 1
  num_men[i] -= len(E[i])
      
print(*num_men)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import copy 

N ,M ,K = [int(i) for i in input().split(' ')]
AB = defaultdict(deque)

arrive = [-1] * N

for _ in range(M):
    a, b = [int(i) for i in input().split(' ')]
    AB[a].append(b)
    AB[b].append(a)

CD = defaultdict(list)
for _ in range(K):
    c, d = [int(i) for i in input().split(' ')]
    CD[c].append(d)
    CD[d].append(c)

def DFS_size(s, Graph):
    stack = deque([s])
    global arrive
    size = 1
    tree = set()
    while stack:
        v = stack[-1]
        arrive[v-1] = 1
        tree.add(v)
        if Graph[v]:
            w = Graph[v].popleft()
            if arrive[w-1] == -1:
                if not w in stack:
                    arrive[w-1] =1
                    stack.append(w)
        else:
            stack.pop()

    return tree

tree_all =[]
tree_size = [None] *N
for i in range(1,N+1):
    if arrive[i-1] == -1:
        Graph = copy.deepcopy(AB)
        tree = DFS_size(i,Graph)
        size = len(tree)
        for t in tree:
            tree_size[t-1] = size - 1 - len(AB[t]) - sum(1 for i in CD[t] if i in tree)

print(*tree_size)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, data):
        """
        サイズベースのunion_find
        与えられたdataまでの長さの配列を作成
        配列は1から開始する
        それがunionfindの親となり初めは自分自身
        またsizeも定義し初期値は1
        ・union findのグループのサイズの求め方
        1.あるxのグループの親を取得
        union_find = UnionFind(N)
        par_x = union_find.find(x)
        2.その親のsizeがそのグループのサイズになっている
        size = union_find.size[par_x]
        """
        self.parent = {}
        self.size = {}
        for i in range(1, data+1):
            self.parent[i] = i
            self.size[i] = 1


    def find(self, x):
        """
        与えられた値に対してその親ノードを返却
        """
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x]) # self.parentに入れ直しているのは次findするとき高速になるよう再起により親を直接結んでいる
            return self.parent[x]


    def same(self, x, y):
        """
        与えられた2つの値が同一グループ(親)かチェック
        """
        return self.find(x) == self.find(y)


    def unite(self, x, y):
        """
        与えられた2つの値を同一のグループ(親)にする
        """
        x = self.find(x)
        y = self.find(y)
        if x == y: # すでに同じグループなら何もしない
            return
        if self.size[x] > self.size[y]: # ランクが異なる場合小さい方の親を大きい方にする
            self.parent[y] = x
            self.size[x] += self.size[y]
            return
        elif self.size[x] < self.size[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
            return
        else: # ランクが同じ場合どちらかの親にする その際親にした方の値のランクをあげる
            self.parent[x] = y
            if self.size[x] == self.size[y]: self.size[y] += self.size[x]
            return

if __name__ == '__main__':
    N,M,K = map(int, input().split())
    union_find = UnionFind(N)

    kankei = [[] for i in range(N+1)]
    for i in range(M):
        A,B = map(int, input().split())
        union_find.unite(A,B)
        if B in kankei[A]:
            continue
        else:
            kankei[A].append(B)
            kankei[B].append(A)

    for i in range(K):
        C,D = map(int, input().split())
        if union_find.same(C,D):
            if D not in kankei[C]:
                kankei[C].append(D)
                kankei[D].append(C)

    ans = ""
    for i in range(1,N+1):
        ans += str(union_find.size[union_find.find(i)]-len(kankei[i])-1) + " "

    print(ans.rstrip())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import copy 

N ,M ,K = [int(i) for i in input().split(' ')]
AB = defaultdict(deque)

arrive_size = [-1] * N

for _ in range(M):
    a, b = [int(i) for i in input().split(' ')]
    AB[a].append(b)
    AB[b].append(a)

CD = defaultdict(list)
for _ in range(K):
    c, d = [int(i) for i in input().split(' ')]
    CD[c].append(d)
    CD[d].append(c)

def DFS_size(s, Graph):
    stack = deque([s])
    size = 1
    arrive = [0] * N
    tree = set()
    while stack:
        v = stack[-1]
        arrive[v-1] = 1
        tree.add(v)
        if Graph[v]:
            w = Graph[v].popleft()
            if arrive[w-1] == 0:
                if not w in stack:
                    arrive[w-1] =1
                    stack.append(w)
        else:
            stack.pop()

    return tree

tree_all =[]
tree_size = [None] *N
for i in range(1,N+1):
    if arrive_size[i-1] == -1:
        Graph = copy.deepcopy(AB)
        tree = DFS_size(i,Graph)
        for t in tree:
            size = len(tree)
            for block in CD[t]:
                if block in tree:
                    size -= 1
            for friend in AB[t]:
                if friend in tree:
                    size -= 1
            tree_size[t-1] = size - 1

print(*tree_size)