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: Wrong Answer

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)]
con = [1 for _ in range(n+1)]
uni = [[i, 1] for i in range(n+1)]
for i in range(m):
    a, b = ab[i]
    con[a] += 1
    con[b] += 1
    if uni[a][0] != uni[b][0]:
        a_root = uni[a][0]
        while a_root != uni[a_root][0]:
            a_root = uni[a_root][0]
        b_root = uni[b][0]
        while b_root != uni[b_root][0]:
            b_root = uni[b_root][0]
        a, b = sorted([a_root, b_root])
        uni[a][1] += uni[b][1]
        uni[b][0] = a

for i in range(k):
    c, d = cd[i]
    while c != uni[c][0]:
        c = uni[c][0]
    while d != uni[d][0]:
        d = uni[d][0]
    if uni[c] == uni[d]:
        con[cd[i][0]] += 1
        con[cd[i][1]] += 1

result = []
for i in range(1, n+1):
    root = uni[i][0]
    while root != uni[root][0]:
        root = uni[root][0]
    result.append(uni[root][1]-con[i])
print(*result)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

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

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

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

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

def resolve():
    int1 = lambda x: int(x) - 1
    readline=sys.stdin.readline

    n,m,k=map(int, readline().strip().split())

    uf = UnionFind(n)

    exc=[0]*n

    for i in range(m):
        a,b=map(int1, readline().strip().split())
        uf.Unite(a,b)
        exc[a]+=1
        exc[b]+=1
    
    for i in range(k):
        a,b=map(int1, readline().strip().split())
        if uf.isSameGroup(a,b):
            exc[a]+=1
            exc[b]+=1
    
    rescnt=[]

    for i in range(n):
        ri=uf.Count(i)-1-exc[i]
        rescnt.append(str(ri))
    
    print(" ".join(rescnt))

#resolve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
# sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = True
show_flg = False


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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots()),


def bfs(graph, initial, goal):
    n = len(graph) - 1
    q = deque([initial])
    visited = [False] * (n + 1)
    visited[initial] = True

    while len(q) != 0:
        edge = q.popleft()
        nxt = graph[edge]

        for i, e in enumerate(nxt):
            if visited[e] is False:
                if goal == e:
                    return True
                q.append(e)
                visited[e] = True

    return False


def main():
    N, M, K = MI()
    A = [0] * M
    B = [0] * M
    C = [0] * K
    D = [0] * K
    uf = UnionFind(N+1)
    friends = {k: set() for k in range(1, N+1)}
    blocks = {k: set() for k in range(1, N+1)}
    # graph = [[] for i in range(N+1)]

    for i in range(M):
        A[i], B[i] = MI()
        friends[A[i]].add(B[i])
        friends[B[i]].add(A[i])
        # graph[A[i]].append(B[i])
        # graph[B[i]].append(A[i])
        uf.union(A[i], B[i])
        # s1 = min(A[i], B[i])
        # s2 = max(A[i], B[i])
        # graph[s1].append(s2)

    for i in range(K):
        C[i], D[i] = MI()
        blocks[C[i]].add(D[i])
        blocks[D[i]].add(C[i])

    # print(friends)
    # print(blocks)

    groups = {k: set(g) for k, g in uf.all_group_members().items()}

    ans = [0] * N
    for i in range(1, N+1):
        # print(i, uf.members(i), friends[i], blocks[i])
        node = uf.find(i)
        members = groups[node]
        # members = members - blocks[i]
        # members = set(members)
        ans[i-1] = len(members) - len(friends[i]) - 1

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest

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

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

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

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

def resolve():
    n,m,k=map(int, sys.stdin.readline().strip().split())
    #list(map(int,input().strip().split()))

    uf = UnionFind(n)

    res=[[] for i in range(n)]
    frd=[0 for i in range(n)]
    blk=[0 for i in range(n)]

    for i in range(m):
        #a,b=list(map(int,input().strip().split()))
        a,b=map(int, sys.stdin.readline().strip().split())
        a-=1
        b-=1
        uf.Unite(a,b)
        frd[a]+=1
        frd[b]+=1
    
    for i in range(k):
        #a,b=list(map(int,input().strip().split()))
        a,b=map(int, sys.stdin.readline().strip().split())
        a-=1
        b-=1
        if uf.isSameGroup(a,b):
            blk[a]+=1
            blk[b]+=1
    
    rescnt=[]

    for i in range(n):
        ri=uf.Count(i)-1-blk[i]-frd[i]
        rescnt.append(str(ri))
        ##rescnt.append(str(n-uf.size(i)-len(blk[i])))
    
    print(" ".join(rescnt))

#resolve()

Submission status: Wrong Answer

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)
not_friend_candidates = [1]*N
for _ in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)
    not_friend_candidates[A-1] += 1
    not_friend_candidates[B-1] += 1
for _ in range(K):
    C, D = map(int, input().split())
    not_friend_candidates[C-1] += 1
    not_friend_candidates[D-1] += 1
for hito in range(N):
    print(uf.size(hito) - not_friend_candidates[hito], end=" ")
print()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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


#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x]=y

li1 = [i for i in range(N)]
li2 = [i for i in range(N)]

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    print(str(i)+" ",end="")
    union(min(a-1,b-1),max(a-1,b-1),li1)
# for i in range(K):
#     c = CD[i][0]
#     d = CD[i][1]
#     union(c-1,d-1,li2)

mm = [0 for i in range(max(li1)+1)]
for i in range(N):
    m = root(i,li1)
    mm[m] += 1

print(li1)
print(mm)
ans = [mm[li1[i]]-1 for i in range(N)]
# print(ans)

for i in range(M):
    a = AB[i][0]
    b = AB[i][1]
    ans[a-1] -= 1
    ans[b-1] -= 1


for i in range(K):
    c = CD[i][0]
    d = CD[i][1]
    if find(c-1,d-1,li1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

Submission status: Wrong Answer

Solution code:

class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[-1]*node_size
 
        self.size = [1] * node_size
        self.rank = [1] * node_size
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == -1:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
            else:
                self.parent[root_node0] = root_node1

            self.size[root_node0] += self.size[root_node1]

    def same(self,node0,node1):
        #同じグループか確かめる
        return self.find_root(node0)==self.find_root(node1)


    # def recombind(self,node):
    #     # rootがnodeのものを整理し直す


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

ut = UnionFindTree(N)
friend_dict = {i:[] for i in range(N)}
friend_dict = {i:0 for i in range(N)}

for i in range(M):
    x,y = map(int,input().split())
    x-=1
    y-=1
    ut.unite(x,y)
    friend_dict[x]+=1
    friend_dict[y]+=1
    # friend_dict[x].extend([y])
    # friend_dict[y].extend([x])

# for i in range(N):
#     ut.find_root(i)

# block_dict = {i:[] for i in range(N)}
block_dict = {i:0 for i in range(N)}

for i in range(K):
    x,y = map(int,input().split())
    x-=1
    y-=1
    if ut.same(x,y):
        block_dict[x]+=1
        block_dict[y]+=1
        # block_dict[x].extend([y])
        # block_dict[y].extend([x])

ans =""
for i in range(N):
    group =  ut.find_root(i)
    group_size = ut.size[group]

    # cand = group_size - len(friend_dict[i]) - len(block_dict[i])
    cand = group_size - friend_dict[i] - block_dict[i] - 1
    ans += str(cand) + " "
print(ans)

Submission status: Wrong Answer

Solution code:

class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[-1]*node_size
 
        self.size = [1] * node_size
        self.rank = [1] * node_size
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == -1:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
            else:
                self.parent[root_node0] = root_node1

            self.size[root_node0] += self.size[root_node1]

    def same(self,node0,node1):
        #同じグループか確かめる
        return self.find_root(node0)==self.find_root(node1)


    # def recombind(self,node):
    #     # rootがnodeのものを整理し直す


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

ut = UnionFindTree(N)
friend_dict = {i:[] for i in range(N)}
friend_dict = {i:0 for i in range(N)}

for i in range(M):
    x,y = map(int,input().split())
    x-=1
    y-=1
    ut.unite(x,y)
    friend_dict[x]+=1
    friend_dict[y]+=1
    # friend_dict[x].extend([y])
    # friend_dict[y].extend([x])

# for i in range(N):
#     ut.find_root(i)

# block_dict = {i:[] for i in range(N)}
block_dict = {i:0 for i in range(N)}

for i in range(K):
    x,y = map(int,input().split())
    x-=1
    y-=1
    if ut.same(x,y):
        block_dict[x]+=1
        block_dict[y]+=1
        # block_dict[x].extend([y])
        # block_dict[y].extend([x])

ans =""
for i in range(N):
    group =  ut.find_root(i)
    group_size = ut.size[group]

    # cand = group_size - len(friend_dict[i]) - len(block_dict[i])
    cand = group_size - friend_dict[i] - block_dict[i] - 1
    ans += str(cand) + " "
print(ans[:-1])

Submission status: Wrong Answer

Solution code:

class UnionFindTree():
    # Union find tree
    # 2つの効率化　経路圧縮、ランク
    # つなげることはできるか分離することはできないので、木をつなげる方向に利用する
    # 
    def __init__(self, node_size):
        # node_num: 全体のノード数
        # parent: ノードがrootなら-1、親がいれば親の番号を入れる
        # size:
        # rank:  
        # self.parent =[-1] * node_size
        self.parent =[-1]*node_size
 
        self.size = [1] * node_size
        self.rank = [1] * node_size
    
    def find_root(self,node):
        # node属する木のrootを探す
        # たどった経路に含まれるnodeの親をrootにつなぎ替える
        if self.parent[node] == -1:             # 自身がrootの場合
            root = node
        else:                                   # 自身がrootでない場合
            root = self.find_root(self.parent[node]) # 再帰的にrootを探す
            self.parent[node] = root            # たどった経路に含まれるnodeの親をrootにつなぎ替える(経路圧縮)
        return root

    def unite(self,node0, node1):
        # node0とnode1が含まれる木を結合する
        
        #node0 node1のrootを求める
        root_node0 = self.find_root(node0) 
        root_node1 = self.find_root(node1)

        if root_node0 != root_node1:
            # rankを比較しrankが小さい方の木を大きい方の木のrootにつなげる
            # rank is sameのときのみrankが増える
            if self.rank[root_node0] == self.rank[root_node1]: # rank is same
                self.parent[root_node1] = root_node0
                self.rank[root_node0] += 1
            elif self.rank[root_node0] > self.rank[root_node1]:
                self.parent[root_node1] = root_node0
            else:
                self.parent[root_node0] = root_node1

            self.size[root_node0] += self.size[root_node1]

    def same(self,node0,node1):
        #同じグループか確かめる
        return self.find_root(node0)==self.find_root(node1)


    # def recombind(self,node):
    #     # rootがnodeのものを整理し直す


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

ut = UnionFindTree(N)
friend_dict = {i:[] for i in range(N)}
friend_dict = {i:0 for i in range(N)}

for i in range(M):
    x,y = map(int,input().split())
    x-=1
    y-=1
    ut.unite(x,y)
    friend_dict[x]+=1
    friend_dict[y]+=1
    # friend_dict[x].extend([y])
    # friend_dict[y].extend([x])

for i in range(N):
    ut.find_root(i)

# block_dict = {i:[] for i in range(N)}
block_dict = {i:0 for i in range(N)}

for i in range(K):
    x,y = map(int,input().split())
    x-=1
    y-=1
    if ut.same(x,y):
        block_dict[x]+=1
        block_dict[y]+=1
        # block_dict[x].extend([y])
        # block_dict[y].extend([x])

ans =""
for i in range(N):
    group =  ut.find_root(i)
    group_size = ut.size[group]

    # cand = group_size - len(friend_dict[i]) - len(block_dict[i])
    cand = group_size - friend_dict[i] - block_dict[i] - 1
    ans += str(cand) + " "
print(ans[:-1])

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import queue

def main():
    n, m, k = map(int, input().split())
    fri = [[0, []] for _ in range(n)]
    group = []
    for _ in range(m):
        one, ano = map(int, input().split())
        fri[one-1][1].append(ano)
        fri[ano-1][1].append(one)
        
    for i in range(n):
        if fri[i][0] != 0:
            continue
        group_cnt = 0
        q = queue.Queue()
        q.put(i)
        while not q.empty():
            person = q.get()
            for p in fri[person-1][1]:
                if fri[p-1][0] != 0:
                    continue
                q.put(p)
                fri[p-1][0] = len(group) + 1
                group_cnt += 1
        group.append(group_cnt)
    
    res = [0 for _ in range(n)]
    for i in range(n):
        group_id = fri[i][0] - 1
        res[i] = group[group_id] - len(fri[i][1]) - 1
        
    for _ in range(k):
        one, ano = map(int, input().split())
        if fri[one-1][0] == fri[ano-1][0]:
            res[one-1] -= 1
            res[ano-1] -= 1
    print(' '.join([str(num) for num in res]))

            
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)

friend_dic = {}
block_dic = {}
results = {}
N, M, K = map(int, input().split())

for i in range(1, N+1):
    friend_dic[i] = []
    block_dic[i] = []
    results[i] = None

for _ in range(M):
    a, b = map(int, input().split())
    friend_dic[a].append(b)
    friend_dic[b].append(a)

for _ in range(K):
    a, b = map(int, input().split())
    block_dic[a].append(b)
    block_dic[b].append(a)

def dfs(graph, start, cluster):
    cluster.append(start)
    for neighbor in graph[start]:
        if neighbor not in cluster:
            dfs(graph, neighbor, cluster)


result = []
for i in range(1, N+1):
    if results[i] is not None:
        result += results[i]
    else:
        cluster = []
        dfs(friend_dic, i, cluster)
        for v in cluster:
            results[v] = str(len(set(cluster) - set(friend_dic[v]) - set(block_dic[v])) - 1)
        result += results[i]
print(" ".join(result))

Submission status: Wrong Answer

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


if __name__ == "__main__":
    pass
    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 - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

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

    visited = set()
    conns = []
    for i in range(n):
        if i not in visited:
            conn = dfs(graph_f, i)
            visited |= conn
            conns.append(conn)

    res = []
    for i in range(n):
        suggestion_cnt = 0
        current_conn = list(filter(lambda x: i in x, conns))[0]
        for j in range(1, n + 1):
            if i == j:
                continue
            else:
                if j in current_conn and j not in graph_f[i] and j not in graph_b[i]:
                    suggestion_cnt += 1
        res.append(suggestion_cnt)

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

Submission status: Wrong Answer

Solution code:
import bisect


class UnionFind():
    
    def __init__(self, n):
        self.n = next
        self.parent = [-1 for i in range(n)]
    
    def find(self, x):
        if self.parent[x] < 0:
            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:
            return False
        else:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            return True
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parent[self.find(x)]
    
    def __str__(self):
        return str(self.parent)



def read():
    N, M, K = list(map(int, input().strip().split()))
    uf = UnionFind(N)
    friends = [list() for i in range(N+1)]
    blocked = [list() for i in range(N+1)]
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        friends[a].append(b)
        friends[b].append(a)
        uf.unite(a-1, b-1)
    for i in range(K):
        c, d = list(map(int, input().strip().split()))
        blocked[c].append(d)
        blocked[d].append(c)
    for i in range(N+1):
        friends[i] = sorted(friends[i])
        blocked[i] = sorted(blocked[i])
    return N, M, K, friends, blocked, uf


def solve(N, M, K, friends, blocked, uf):
    n_friendships = [0 for i in range(N)]
    for i in range(N):
        for j in friends[i]:
            bi = bisect.bisect_left(blocked[i+1], j+1)
            is_blocked = bi < len(blocked[i+1]) and blocked[i+1][bi] == j+1
            if not is_blocked:
                n_friendships[i] += 1
    return ' '.join(map(str, n_friendships))


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, M, K = map(int, input().split())
friendly = list()
no_friendly = list()
for i in range(M):
    friendly.append(list(map(int, input().split())))
for i in range(K):
    no_friendly.append(list(map(int, input().split())))

friendly_dict = dict()
no_friendly_dict = dict()
for i in range(M):
    a = friendly[i][0]
    b = friendly[i][1]
    if a not in friendly_dict.keys():
        friendly_dict[a] = [b]
    else:
        friendly_dict[a].append(b)
    if b not in friendly_dict.keys():
        friendly_dict[b] = [a]
    else:
        friendly_dict[b].append(a)
for i in range(K):
    a = no_friendly[i][0]
    b = no_friendly[i][1]
    if a not in no_friendly_dict.keys():
        no_friendly_dict[a] = [b]
    else:
        no_friendly_dict[a].append(b)
    if b not in no_friendly_dict.keys():
        no_friendly_dict[b] = [a]
    else:
        no_friendly_dict[b].append(a)

group = [0 for i in range(N+1)]
for i in range(1,N+1):
    if group[i] == 0:
        group[i] = i
    try:
        for k in friendly_dict[i]:
            if group[k] == 0:
                group[k] = i
            else:
                group[i] = min([group[i], group[k]])
                group[k] = min([group[i], group[k]])
    except KeyError:
        pass

count = Counter(group)
kouho = [0 for i in range(N+1)]
for i in range(1, N+1):
    try:
        kouho[i] = count[group[i]] - len(friendly_dict[i]) -1
        for k in no_friendly_dict[i]:
            if group[k] == group[i]:
                kouho[i] -= 1
    except KeyError:
        pass
print(' '.join(map(str, kouho[1:])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
total=0
def bfs(ind,num):
    kouho=friends[ind]
    
    for i in kouho:
        if sans[i]!=-1:
            continue
        num+=1
        sans[i]=sans[ind]
        l[sans[ind]].append(i)
        num+=bfs(i,0)
    return num
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[[i] for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
total=bfs(0,total)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    total=bfs(i,total)
ans=[0 for _ in range(n)]


for i in range(n):
    l[i]=set(l[i])

"""
for i in range(n):
    tmp=l[sans[i]]-block[i]
    ans[i]=len(tmp)-len(friends[i])-1
"""

ans=" ".join(map(str,ans))
#print("total:",total)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
total=0
def bfs(ind,num):
    kouho=friends[ind]
    
    for i in kouho:
        if sans[i]!=-1:
            continue
        num+=1
        sans[i]=sans[ind]
        l[sans[ind]].append(i)
        num+=bfs(i,0)
    return num
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[[i] for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
total=bfs(0,total)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    total=bfs(i,total)
ans=[0 for _ in range(n)]

"""
for i in range(n):
    l[i]=set(l[i])


for i in range(n):
    tmp=l[sans[i]]-block[i]
    ans[i]=len(tmp)-len(friends[i])-1
"""

ans=" ".join(map(str,ans))
#print("total:",total)
print(ans)