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:
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:
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    self.parents[y] = x
  
  def members(self, x):
    root = self.find(x)
    zz={i for i in range(self.n) if self.find(i) == root}
    zz.discard(x)
    return zz
  
  def roots(self):
    return {i for i, x in enumerate(self.parents) if x < 0}
  
  def all_group_members(self):
    return {r: self.members(r) for r in range(n)}

n,m,k=map(int,input().split())
uf=UnionFind(n)
fr=[set() for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].add(b-1)
  fr[b-1].add(a-1)
  uf.union(a-1,b-1)
br=[set() for _ in range(n)]
for i in range(k):
  a,b=map(int,input().split())
  br[a-1].add(b-1)
  br[b-1].add(a-1)
d=uf.all_group_members()
ans=[0]*n
for i in range(n):
  ans[i]=len(d[i])-len(d[i]&br[i])-len(fr[i])
print(*ans)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
A = [[0] * N for i in range(N)] 
for i in range(M):
  p, q = map(int, input().split())
  A[p - 1][q - 1] = 1
  A[q - 1][p - 1] = 1
for i in range(K):
  p, q = map(int, input().split())
  A[p - 1][q - 1] = -1
  A[q - 1][p - 1] = -1
T = 1
while T > 0:
  T = 0
  for i in range(N):
    for j in range(N):
      for k in range(N):
        if i != j and i != k and j != k and A[i][j]>0 and A[i][k]>0 and A[j][k] == 0:
          A[j][k] = 2
          T = T + 1
B = [0] * N 
for i in range(N):
  c = 0
  for j in range(N):
    if A[i][j] == 2:
      c = c + 1
    B[i] = c
B_1 = [str(a) for a in B]
B_1 = " ".join(B_1)
print(B_1)

Submission status: Wrong Answer

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

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

Solution code:
from collections import deque


n, m, k = list(map(int, input().split()))
friends = [tuple(map(int, input().split())) for _ in range(m)]
block = [tuple(map(int, input().split())) for _ in range(k)]

relation_d = {}
for i in range(1, n+1):
    relation_d[str(i)] = set()
for a, b in friends:
    relation_d[str(a)].add(str(b))
    relation_d[str(b)].add(str(a))

block_d = {}
for i in range(1, n+1):
    block_d[str(i)] = set()
for a, b in block:
    block_d[str(a)].add(str(b))
    block_d[str(b)].add(str(a))


for i in range(1, n+1):
    visited = set()
    candidates = set()
    dq = deque(list(relation_d[str(i)]))
    while dq:
        for j in range(len(dq)):
            node = dq.popleft()
            if not node in relation_d[str(i)]:
                candidates.add(node)
            if not node in visited:
                dq.extend(relation_d[node])
            visited.add(node)
    print(len(candidates-block_d[str(i)]-set(str(i))), end=" ")

    #print(relation_d[str(i)], block_d[str(i)], relation_d[str(i)]-block_d[str(i)])
    # print(len(candidates-block_d[str(i)]))
    # print(len(member-relation_d[str(i)]-block_d[str(i)])-1, end=" ")
    # print(n-1-len(relation_d[str(i)]-block_d[str(i)]), end=" ")

Submission status: Wrong Answer

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

result = [0]*N
ls = [[True]*N for _ in range(N)]
for i in range(N):
    ls[i][i] = False

A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    ls[A[i]-1][B[i]-1] = False
    ls[B[i]-1][A[i]-1] = False

C = [0]*K
D = [0]*K
for i in range(K):
    C[i], D[i] = map(int, input().split())
    ls[C[i]-1][D[i]-1] = False
    ls[D[i]-1][C[i]-1] = False

for i in range(N):
    visit = [i+1]
    candi = set()
    now = 0
    while True:
        if ls[i][visit[now]-1] == True:
            result[i] += 1

        for j in range(M):
            if visit[now] == A[j] and B[j] not in visit:
                visit += [B[j]]
            if visit[now] == B[j] and A[j] not in visit:
                visit += [A[j]]
        if len(visit) == now+1:
            break

        now += 1
            

print(result)

Submission status: Wrong Answer

Solution code:
n, m, k = list(map(int, input().split()))
ms = {}
for _ in range(m):
    a, b = list(map(int, input().split()))
    ms[a] = ms.get(a, set())
    ms[a].add(b)
    ms[b] = ms.get(b, set())
    ms[b].add(a)

ks = {}
for _ in range(k):
    c, d = list(map(int, input().split()))
    ks[c] = ks.get(c, set())
    ks[c].add(d)
    ks[d] = ks.get(d, set())
    ks[d].add(c)

num_cand = []
for i in range(1, n+1):
    cnt = len([j for j in range(1, n+1)
               if j != i and
               (i not in ms or j not in ms[i]) and \
               (i not in ks or j not in ks[i])
               ])
    num_cand.append(str(cnt))
print(" ".join(num_cand))

Submission status: Wrong Answer

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

n = int(n)

m = int(m)

k = int(k)

friend_dict = {}

block_dict = {}

for i in range(m):
    mm = list(map(int,input().split()))
    # print(mm)
    if mm[0] in friend_dict:
        friend_dict[mm[0]].append(mm[1])
    else:
        friend_dict[mm[0]] = [mm[1]]
    if mm[1] in friend_dict:
        friend_dict[mm[1]].append(mm[0])
    else:
        friend_dict[mm[1]] = [mm[0]]

for j in range(k):
    kk = list(map(int,input().split()))
    if kk[0] in block_dict:
        block_dict[kk[0]].append(kk[1])
    else:
        block_dict[kk[0]] = [kk[1]]
    if kk[1] in block_dict:
        block_dict[kk[1]].append(kk[0])
    else:
        block_dict[kk[1]] = [kk[0]]

# print(friend_dict)
#
# print(block_dict)

for z in range(1, n+1):
    friends = -1
    if z in friend_dict:
        friends = n - 1 - len(friend_dict[z])
    else:
        friends = n - 1
    if z in block_dict:
        friends -= len(block_dict[z])
    print(str(friends), end = ' ')

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
n_list = [(n-1) for i in range(n)]

for i in range(m):
  a_list = list(map(int,input().split()))
  for a in a_list:
    n_list[a -1] -=1
for b in range(k):
  a_list = list(map(int,input().split()))
  for a  in a_list:
    n_list[a -1] -= 1    

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

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 =[node for node in range(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] == node:             # 自身が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]


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

ut = UnionFindTree(N)
friend_dict = {i:[] 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].extend([y])
    friend_dict[y].extend([x])
for _ in range(max(ut.rank)):
    for i in range(N):
        ut.find_root(i)

block_dict = {i:[] for i in range(N)}
for i in range(K):
    x,y = map(int,input().split())
    x-=1
    y-=1
    if ut.parent[x]==ut.parent[y]:
        block_dict[x].extend([y])
        block_dict[y].extend([x])

ans =""
for i in range(N):
    group =  ut.parent[i]
    group_size = ut.size[group]
    cand = group_size - len(friend_dict[i]) - len(block_dict[i])
    ans += str(cand-1) + " "
print(ans[:-1])

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, m, k = map(int, input().split(" "))
    array = [0] * n
    for _ in range(m):
        i, j = map(int, sys.stdin.readline().strip().split(" "))
        array[i - 1] += 1
        array[j - 1] += 1
    for _ in range(k):
        i, j = map(int, sys.stdin.readline().strip().split(" "))
        array[i - 1] += 1
        array[j - 1] += 1
    ans = map(lambda i: str(n - 1 - i), array)
    print(" ".join(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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)]
FR = [[False]*n for i in range(n)]
NOTFR = [[False]*n for i in range(n)]
for i in range(m):
  FR[AB[i][0]-1][AB[i][1]-1] = True
  FR[AB[i][1]-1][AB[i][0]-1] = True
for i in range(k):
  NOTFR[CD[i][0]-1][CD[i][1]-1] = True
  NOTFR[CD[i][1]-1][CD[i][0]-1] = True
L = [0]*n
for i in range(n-1):
  for j in range(i+1,n):
      if FR[i][j] is not True and NOTFR[i][j] is not True:
        flag = True
        for k in range(i, j):
          if FR[k][k+1] is not True:
            flag = False
        if flag:
          L[i] += 1
          L[j] += 1
print(*L)

Submission status: Wrong Answer

Solution code:
import sys

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]
#     union(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))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-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:
V,E,K=map(int,input().split())
edges=[set() for i in range(V)]
edged=[set() for i in range(V)]
ans = [0]*V
for i in range(E):
    a,b=map(int,input().split())
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
for i in range(K):
    c,d=map(int,input().split())
    edged[c-1].add(d-1)
    edged[d-1].add(c-1)
for i in range(V):
    ans[i] =len({n for v in edges[i] for n in edges[v] if not n in edges[i] and n!=i and not n in edged[i]})
print(*ans, sep=" ")

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
ab = {i + 1: [] for i in range(n)}
cd = {i + 1: [] for i in range(n)}
for i in range(m):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)
for i in range(k):
    c, d = map(int, input().split())
    cd[c].append(d)
    cd[d].append(c)
for i in range(n):
    link = set()
    checked = set()
    check_list = [i + 1]
    while check_list:
        check = check_list.pop(0)
        checked |= {check}
        temp = ab[check]
        for j in temp:
            if j not in checked:
                check_list.append(j)
            if j in cd[i + 1]:
                continue
            else:
                if j not in ab[i + 1]:
                    link |= set([j])
    print(len(link) - 1, end = " ")

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

uf_friend = UnionFind(N)

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict


graph = defaultdict(set)
banned = defaultdict(set)

N, M, K = map(int, input().split())
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)


res = [0] * (N + 1)
seen1 = defaultdict(set)
for i in range(1, N + 1):
    queue = deque([i])
    seen = {i}
    while queue:
        cur = queue.popleft()
        if i != cur and cur not in graph[i] and cur not in banned[i]:
            res[i] += 1
            res[cur] += 1
            seen1[cur].add(i)
        for nxt in graph[cur]:
            if nxt not in seen and nxt not in seen1[i]:
                seen.add(nxt)
                queue.append(nxt)
print(*res[1:])

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        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

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




N, M, K = MAP()
F = [LIST() for i in range(M)]
B = [LIST() for i in range(K)]

R = [[0] * N for i in range(N)]

for i, j in F:
    R[i-1][j-1] = 1
    R[j-1][i-1] = 1
for i, j in B:
    R[i-1][j-1] = 2
    R[j-1][i-1] = 2

for i in range(N):
    R[i][i] = 3
# print(R)
ans = []
# print(*R,sep="\n")
for r in R:
    cnt = 0
    for y in r:
        if y == 0:
            cnt += 1
    ans.append(cnt)
print(*ans)


    



exit()
tree_friend = UnionFind(N)
tree_block = UnionFind(N)

for a, b in F:
    # if p == 0:
    #     tree.unite(a, b)
    #else:
    tree_friend.unite(a-1, b-1)
    # tree_friend.unite(b-1, a-1)
    #     print("Yes")
    # else:
    #     print("No")

for a, b in B:
    tree_block.unite(a-1, b-1)
    # tree_block.unite(b-1, a-1)


# for i in range(M):
#     for j in range(K):
#         tree_block

# print(tree_friend.find(3))
# print(tree_block.find(3))
print("a")
for i in range(N):
    x = tree_friend.find(i)
    y = tree_block.find(i)
    print(x, y)

Submission status: Wrong Answer

Solution code:
N,M,K = map(int,input().split())
AB = []
for _ in range(M):
    AB.append([int(i) for i in input().split()])
CD = []
for _ in range(K):
    CD.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
friend = ddict(list)
for ab in AB:
    friend[ab[0]].append(ab[1])
    friend[ab[1]].append(ab[0])
block = ddict(list)
for cd in CD:
    block[cd[0]].append(cd[1])
    block[cd[1]].append(cd[0])
from collections import deque
group = []
done = set()
for n in range(1,N):
    if n in done:
        pass
    else:
        group.append([])
        q = deque([n])
        while q:
            target = q.pop()
            for f in friend[target]:
                if f not in group[-1]:
                    q.append(f)
                    group[-1].append(f)
                    done.add(f)
group_fix = []
for g in group:
    group_fix.append(set(g))
ans = []
for n in range(1,N+1):
    for g in group_fix:
        if n in g:
            temp = g - set(block[n])
            temp = temp - set(friend[n])
            temp = temp - set([n])
            ans.append(len(temp))
            break
        else:
            pass
print(*ans)

Submission status: Wrong Answer

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce


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

    ary = []
    block = []
    links = []

    for _ in range(N):
        ary.append(set())
        block.append(set())
        links.append([False] * N)

    for _ in range(M):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        ary[A].add(B)
        ary[B].add(A)

    for _ in range(K):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        block[A].add(B)
        block[B].add(A)

    def search(n, s):
        s.add(n)
        for i in ary[n]:
            if not i in s:
                search(i, s)
    ans = []
    for i in range(N):
        ans.append(N - len(ary[i]) - len(block[i]) - 1)
    ans = " ".join(map(str, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def solve():
    N, M, K = map(int,input().split())
    P = {i:i for i in range(1,N+1)}
    E = {i:{i,} for i in range(1,N+1)}
    for _ in range(M):
        a, b = map(int,input().split())
        a, b = min(a,b), max(a,b)
        if P[b] == b:
            P[b] = a
        else:
            P[a] = b
        E[a].add(b)
        E[b].add(a)

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

    G = {i:{i,} for i in range(1,N+1) if P[i]==i}
    C = set(G.keys())
    for i in range(1,N+1):
        v = i
        l = set()
        while v not in C:
            l.add(v)
            v = P[v]
        for u in l:
            P[u] = P[v]
        G[P[v]] |= l
        C |= l

    res = ' '.join(map(str, (len(G[P[i]] - E[i]) for i in range(1,N+1))))
    return res

if __name__ == '__main__':
    print(solve())

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 =[node for node in range(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] == node:             # 自身が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]


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

ut = UnionFindTree(N)
friend_dict = {i:[] 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].extend([y])
    friend_dict[y].extend([x])

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

block_dict = {i:[] for i in range(N)}
for i in range(K):
    x,y = map(int,input().split())
    x-=1
    y-=1
    if ut.parent[x]==ut.parent[y]:
        block_dict[x].extend([y])
        block_dict[y].extend([x])

ans =""
for i in range(N):
    group =  ut.parent[i]
    group_size = ut.size[group]
    cand = group_size - len(friend_dict[i]) - len(block_dict[i])
    ans += str(cand-1) + " "
print(ans[:-1])

Submission status: Wrong Answer

Solution code:
V,E,K=map(int,input().split())
edges=[set() for i in range(V)]
edged=[set() for i in range(V)]
ans = [0]*V
for i in range(E):
    a,b=map(int,input().split())
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
for i in range(K):
    c,d=map(int,input().split())
    edged[c-1].add(d-1)
    edged[d-1].add(c-1)
print(edges)
print(edged)
for i in range(V):
    ans[i] =len({n for v in edges[i] for n in edges[v] if not n in edges[i] and n!=i and not n in edged[i]})
print(*ans, sep=" ")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def solve():
    N, M, K = map(int,input().split())
    P = {i:i for i in range(1,N+1)}
    E = {i:{i,} for i in range(1,N+1)}
    for _ in range(M):
        a, b = map(int,input().split())
        a, b = min(a,b), max(a,b)
        if P[b] == b:
            P[b] = a
        else:
            P[a] = b
        E[a].add(b)
        E[b].add(a)

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

    G = {i:{i,} for i in range(1,N+1) if P[i]==i}
    C = set(G.keys())
    for i in range(1,N+1):
        v = i
        l = set()
        while v not in C:
            l.add(v)
            v = P[v]
        for u in l:
            P[u] = P[v]
        G[P[v]] |= l
        C |= l

    print(G,P, E)
    res = ' '.join(map(str, (len(G[P[i]] - E[i]) for i in range(1,N+1))))
    return res

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
import sys

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:
        print(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]
    union(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))]
for i in range(N):
    m = root(i,li1)
    mm[m-1] += 1

# print(li1)
# print(mm)
ans = [mm[li1[i]-1]-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:
N, M, K = list(map(int, input().split()))
mat = [[0]*N for _ in range(N)]
C = {i:[] for i in range(N)}
for _ in range(M):
    a,b = list(map(int, input().split()))
    mat[a-1][b-1] = 1
    mat[b-1][a-1] = 1
    C[a-1].append(b-1)
    C[b-1].append(a-1)

for _ in range(K):
    c,d = list(map(int, input().split()))
    mat[c-1][d-1] = -1
    mat[d-1][c-1] = -1
    
new = [[0]*N for _ in range(N)]

def nex(cur, org):
    global prev
    for n in C[cur]:
        print(cur, n)
        if org!=n and [cur,n] not in prev:
            prev.append([cur,n])
            prev.append([n,cur])
            if mat[cur][n]==1:
                if mat[org][n]==0:
                    new[org][n] = 1
                nex(n, org)
    return 0
    
for i in range(N):
    prev = []
    nex(i, i)
print(' '.join([str(sum(new[i])) for i in range(N)]))

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M, K = LI()
AB = []
CD = []
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    AB.append([a,b])
for k in range(K):
    c, d = LI()
    c -= 1
    d -= 1
    CD.append([c,d])
direct_friend = {}
blocked = {}
relation = [[] for i in range(N)]
for i in range(N):
    direct_friend[i] = []
    blocked[i] = []
for i in range(M):
    a,b = AB[i]
    direct_friend[a].append(b)
    direct_friend[b].append(a)
for i in range(K):
    c,d = CD[i]
    blocked[c].append(d)
    blocked[d].append(c)

def dfs(node, p, cluster):
    cluster.append(node)
    if direct_friend[node] == [p]:
        return cluster
    for new_node in direct_friend[node]:
        if new_node == p:continue
        elif new_node in cluster:continue
        else:
            return dfs(new_node, node, cluster)

for i in range(N):
    if len(relation[i]) == 0:
        cluster = dfs(i, -1, [])
        # print(cluster)
        if cluster == None:
            relation[i] = []
        else:   
            for j in cluster:
                relation[j] = cluster

# print(relation)
# print(direct_friend)
# print(blocked)

for i in range(N):
    blocked[i] = set(blocked[i])
    direct_friend[i] = set(direct_friend[i])

# for i in range(N):
#     if len(direct_friend[n]) == 0:

ans = []
for n in range(N):
    ans.append(len(set(relation[n]) - direct_friend[n] - blocked[n] - set([n])))

for a in ans:
    print(a, end = " ")
print("")