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):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        self.rank = [0] * (n + 1)

    def find(self, x):
        # 根の番号を返す(所属する集合を確認する)
        # ここの再帰をDFSで実装して高速化できるか試す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def size(self,x):
        # 集合のサイズを調べる
        return self.par.count(self.find(x))

    def union(self, vx, vy):
        # 根を探す
        x = self.find(vx)
        y = self.find(vy)
        # rankの小さいものを大きいほうにくっつける
        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

import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    uf.union(a,b)
    out[a].append(b)
    out[b].append(a)

for i in range(k):
    c,d=map(int,input().split())
    if uf.check(c,d):
        out[c].append(d)
        out[d].append(c)
'''
print(out)
print(uf.par)
'''
for i in range(1,n+1):
    ans=uf.size(i)-1-len(out[i])
    print(ans,end=' ')

Submission status: Wrong Answer

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

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

block = []  
for i in range(K):
  c,d = map(int,input().split())
  block.append((c,d))
  
friend_map = [[False for i in range(N)] for j in range(N)]
block_map = [[False for i in range(N)] for j in range(N)]

for i,j in follow:
  friend_map[i-1][j-1] = True
  friend_map[j-1][i-1] = True

for i,j in block:
  block_map[i-1][j-1] = True
  block_map[j-1][i-1] = True

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

for i in range(N):
  for j in range(i,N):
    if i == j:
      continue
    if block_map[i][j]:
      continue
    if friend_map[i][j]:
      continue
    
    for k in range(i,j):
      if not friend_map[k][k+1]:
        break
    else:
      candidate[i] += 1
      candidate[j] += 1

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
N,M,K=map(int,input().split())

class UnionFind():
  def __init__(self,N):
    self.N=N
    self.par=[i for i in range(1,N+1)]
    self.size=[1 for _ in range(N)]
    
  def find(self,x):                
    if self.par[x-1]==x:
      return x
    return self.find(self.par[x-1])
  
  def union(self,x,y):
    if self.par[x-1]==self.par[y-1]:
      pass
    else:
      N=self.N
      x_size=self.size[self.find(x)-1]
      y_size=self.size[self.find(y)-1]
      x_par=self.find(x)
      y_par=self.find(y)
      if x_size<=y_size:
        self.size[y_par-1]+=x_size
        self.size[x_par-1]=0
        for i in range(1,N+1):
          if self.find(i)==x_par:
            self.par[i-1]=y_par
      else:
        self.size[x_par-1]+=y_size
        self.size[y_par-1]=0
        for i in range(1,N+1):
          if self.find(i)==y_par:
            self.par[i-1]=x_par
    return None
  
  def par_size(self):
    return [self.par,self.size]
  
uf=UnionFind(N)

good=defaultdict(list)
bad=defaultdict(list)

for i in range(M):
  x,y=map(int,input().split())
  uf.union(x,y)
  good[x].append(y)
  good[y].append(x)
  
for i in range(K):
  x,y=map(int,input().split())
  bad[x].append(y)
  bad[y].append(x)
  
w=uf.par_size()
par,size=w[0],w[1]

ans=''
for i in range(1,N+1):
  s=size[par[i-1]-1]
  cnt=0
  for j in good[i]:
    if par[i-1]==par[j-1]:
      cnt+=1
  for j in bad[i]:
    if par[i-1]==par[j-1]:
      cnt+=1
  ans+=' '+str(s-cnt-1)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
rt = [0]*n
fr = [0]*n

for x in range(m):
  a,b = map(int, input().split())
  fr[a-1] += 1
  fr[b-1] += 1
  if rt[a-1] == 0 and rt[b-1] == 0:
    rt[a-1] = b
    rt[b-1] = b
  elif rt[b-1] == 0 and rt[a-1] != 0:
    rt[b-1] = rt[a-1]
  elif rt[b-1] != 0 and rt[a-1] == 0:
    rt[a-1] = rt[b-1]
  elif rt[b-1] != rt[a-1]:
    rt = [rt[b-1] if n == rt[a-1] else n for n in rt]

cd = [rt.count(rt[nu])-fr[nu]-1 if rt[nu] != 0 else 0 for nu in range(n)]
    
for y in range(k):
  c,d = map(int, input().split())
  if rt[c-1] == rt[d-1]:
    cd[c-1] -= 1
    cd[d-1] -= 1
print(' '.join(map(str,cd)))

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
rt = [0]*n
fr = [0]*n

for x in range(m):
  a,b = map(int, input().split())
  fr[a-1] += 1
  fr[b-1] += 1
  if rt[a-1] == 0 and rt[b-1] == 0:
    rt[a-1] = b
    rt[b-1] = b
  elif rt[b-1] == 0 and rt[a-1] != 0:
    rt[b-1] = rt[a-1]
  elif rt[b-1] != 0 and rt[a-1] == 0:
    rt[a-1] = rt[b-1]
  elif rt[b-1] != rt[a-1]:
    rt = [rt[b-1] if n == rt[a-1] else n for n in rt]

cd = [rt.count(rt[nu]) if rt[nu] != 0 else 1 for nu in range(n)]
cd = [cd[nu]-fr[nu]-1 for nu in range(n)]
    
for y in range(k):
  c,d = map(int, input().split())
  if rt[c-1] == rt[d-1]:
    cd[c-1] -= 1
    cd[d-1] -= 1
print(' '.join(map(str,cd)))

Submission status: Wrong Answer

Solution code:
n,m,k = map(int,input().split())
ls = [num+1 for num in list(range(n))]
rt = [0]*n
fr = [0]*n

for x in range(m):
  a,b = map(int, input().split())
  fr[a-1] += 1
  fr[b-1] += 1
  if rt[a-1] == 0 and rt[b-1] == 0:
    rt[a-1] = b
    rt[b-1] = b
  elif rt[b-1] == 0 and rt[a-1] != 0:
    rt[b-1] = rt[a-1]
  elif rt[b-1] != 0 and rt[a-1] == 0:
    rt[a-1] = rt[b-1]
  elif rt[b-1] != rt[a-1]:
    rt = [rt[b-1] if n == rt[a-1] else n for n in rt]

cd = [rt.count(rt[nu]) for nu in range(n)]
cd = [cd[nu]-fr[nu]-1 for nu in range(n)]
    
for y in range(k):
  c,d = map(int, input().split())
  if rt[c-1] == rt[d-1]:
    cd[c-1] -= 1
    cd[d-1] -= 1
print(' '.join(map(str,cd)))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    #要素数nで初期化
    #インスタンス変数の初期化
    def __init__(self, n):
        #root : 木の要素数
        #rnk : 木の高さ(rank)
        self.n = n
        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 Union(self, x, y):
        #入力ノードの親を探索
        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が同じ(深さが同じ)場合
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y] += 1
    
    """xとyが同じグループに所属するか"""
    #辺(x,y)が橋の場合 : isSameGroup(self, x, y)=False
    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)]     
    
    """木(非連結成分)の数を数える"""
    #全連結成分にするために必要な橋の本数は、cnt - 1
    def Count_Unconnected_Component(self):
        cnt = 0
        for i in range(self.n):
            if self.root[i+1] < 0:
                cnt += 1
        return cnt
    
    def Members(self, x):
        r = self.Find_Root(x)
        return [i for i in range(self.n+1) if self.Find_Root(i) == r]
    
n,m,k = map(int,input().split())
connect_count = [0]*(1+n)
uf_f = UnionFind(n)
uf_b = UnionFind(n)
for _ in range(m):
    a,b = map(int,input().split())
    connect_count[a] += 1
    connect_count[b] += 1
    uf_f.Union(a,b)
for _ in range(k):
    c,d = map(int,input().split())
    uf_b.Union(c,d)
res = []
for i in range(1,n+1):
    res.append(len(uf_f.Members(i)) - len(uf_b.Members(i)) - connect_count[i])
print(*res)

Submission status: Wrong Answer

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

friends = []
blocks = []
groups = []
fs = [[] for _ in range(n+1)]
bs = [[] for _ in range(n+1)]

for _ in range(m):
    friends.append(tuple(map(int, input().split())))
for _ in range(k):
    blocks.append(tuple(map(int, input().split())))

for i, j in friends:
    fs[i].append(j)
    fs[j].append(i)

for i, j in blocks:
    bs[i].append(j)
    bs[j].append(i)

def search_groups(x, y):
    xx = -1
    yy = -1
    for ind, i in enumerate(groups):
        if x in i:
            xx = ind
            if yy >= 0:
                break
        if y in i:
            yy = ind
            if xx >= 0:
                break
    return xx, yy

for i, j in friends:
    ii, jj = search_groups(i, j)
    if ii==jj==-1:
        groups.append({i, j})
    elif ii==-1:
        groups[jj].add(i)
    elif jj==-1:
        groups[ii].add(j)
    elif ii!=jj:
        rm1 = groups[ii]
        rm2 = groups[jj]
        groups.append(rm1|rm2)
        groups.remove(rm1)
        groups.remove(rm2)

for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(fs[i]) - set(bs[i]))-1, end=' ')
            break

Submission status: Wrong Answer

Solution code:
import sys
N, M, K = map(int, input().split())
F = 2
H = [[0] * (N) for i in range(N)]

# 友達マップ
for i in range(M):
  A, B = map(int, input().split())
  H[A - 1][B - 1] = H[B - 1][A - 1] = F

# ブロックマップ
for i in range(K):
  C, D = map(int, input().split())
  H[C - 1][D - 1] = H[D - 1][C - 1] = -F

# 友達候補探索
def get_friend(parent, target):
  for s in range(N):
    if s != parent and H[parent][s] == 0 and H[target][s] == F:
      #      print ("parent=" + str(parent) + " s=" + str(s))
      H[parent][s] = 1
      get_friend(parent, s)

for i in range(N):
  for j in range(N):
    if i != j and H[i][j] == F:
      get_friend(i, j)
    
#print (H)
c = []
for i in range(N):
  count = 0
  for j in range(N):
    count += H[i][j] % F
  c.append(count)

print (str(c).replace(',', '').replace('[', '').replace(']', ''))

Submission status: Wrong Answer

Solution code:
import itertools

base = list(map(int, input().split(' ')))
N=base[0]
M=base[1]
K=base[2]
terms=[]
for i in range(N):
  term=[]
  for j in range(N):
    term+=[[i,j,0]]
  terms+=[term]
for i in range(M):
  term=list(map(int, input().split(' ')))
  terms[term[0]-1][term[1]-1][2]=1
  terms[term[1]-1][term[0]-1][2]=1
for i in range(K):
  term=list(map(int, input().split(' ')))
  terms[term[0]-1][term[1]-1][2]=-1
  terms[term[1]-1][term[0]-1][2]=-1

for i in range(N):
  counters=0
  for j in range(N):
    counter=0
    if terms[i][j][2]==0 and i!=j:
      sample=[]
      test=[]

      for l in range(N):
        sample+=[l]
      sample.remove(i)
      sample.remove(j)
      
      for l in range(1,N-1):
        test+=list(itertools.permutations(sample,l))
      
      for l in range(len(test)):
        tester=test[l]
        score=terms[i][tester[0]][2]
        count=1
        for m in range(0,len(tester)-1):
          score+=terms[tester[m]][tester[m+1]][2]
          count+=1
        score+=terms[tester[len(tester)-1]][j][2]
        count+=1
        if count==score:
          counter=1
  counters+=counter
  terms[i][i][2]+=counters
  terms[j][j][2]+=counters

for i in range(N):
  print(terms[i][i][2])

Submission status: Wrong Answer

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


import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

a = np.array(e)
n, labels = connected_components(a)

# print(labels)
l = [0] * N
for ll in labels:
    l[ll] += 1

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

ans = []
for i in range(N):
    ans.append(l[labels[i]] - f[i] - 1)

print(*ans)

Submission status: Wrong Answer

Solution code:
i=list(map(int, input().split()))
j=[list(map(int, input().split()))  for l in range(i[1])]
k=[list(map(int, input().split()))  for l in range(i[2])]

s=[0]*i[0]

for l in range(i[0]):
	a=i[0]-1
	for m in range(i[1]):
		if j[m][0]==l+1:
			a-=1
		if j[m][1]==l+1:
			a-=1

	for n in range(i[2]):
		if k[n][0]==l+1:
			a-=1
		if k[n][1]==l+1:
			a-=1

	s[l]=a
    
for l in range(i[0]):
	s[l]=str(s[l])

s=" ".join(s)
print(s)

Submission status: Wrong Answer

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

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

    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)

N, M, K  = (int(i) for i in input().split())

#graph = np.zeros((N+1, N+1))
#graph2 = [[0] * (N+1) for i in range(N+1)]
uf = UnionFind(N)
fblist = [0] * (N+1)

for i in range(M):
    A, B =  (int(i) for i in input().split())
    uf.union(A, B)
    fblist[A] += 1
    fblist[B] += 1
 
for j in range(K):
    A, B =  (int(i) for i in input().split())
    fblist[A] += 1
    fblist[B] += 1

for i in range(1, N+1):
    print(uf.size(i) - fblist[i] - 1, end=" ")

print()

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

class Graph():
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        """ ノードを追加する """
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        # 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
    def remove_edge(self, v1, v2):
        """ ノード同士のつながりを削除する。"""
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)
    def remove_vertex(self,v):
        """ ノードを削除する。"""
        while self.adjacency_dict[v] != []:
            adjacent_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacent_vertex)
        del self.adjacency_dict[v]
    
    def print_graph(self):
        print(self.adjacency_dict)

    def dfs_stack(self, start, visited=None):
            """ 深さ優先探索 Depth First Search スタックバージョン"""
            # ノードを格納するスタック
            stack = [start]
            # 訪れた順番を格納
            visited = []
            
            while stack != []:
                current_vertex = stack.pop()
                visited.append(current_vertex)
                for v in self.adjacency_dict[current_vertex]:
                    if v not in visited and v not in stack:
                        stack.append(v)
            #print(visited)
            return visited

    def bfs(self, start, visited=None):
        # ノードを格納するキュー
        queue = collections.deque([start])
        # 訪れた順番を格納
        visited = []
        while list(queue) != []:
            current_vertex = queue.popleft()
            visited.append(current_vertex)
            for v in self.adjacency_dict[current_vertex]:
                if v not in visited and v not in queue:
                    queue.append(v)
        print(visited)

friend = Graph()
block = Graph()

for i in range(N):
    friend.add_vertex(i+1)
    block.add_vertex(i+1)

for i in range(M):
    friend.add_edge(AB[i][0], AB[i][1])
for i in range(K):
    block.add_edge(CD[i][0], CD[i][1])

ans = [0] * N
for i in range(N):
    #関係全体
    total_related = list(set(friend.dfs_stack(i+1)  + block.dfs_stack(i+1)))
    #直接の友達の数
    friend_number = len(friend.adjacency_dict[i+1])
    #直接のブロックの数
    block_number = len(block.adjacency_dict[i+1])

    ans[i] = len(total_related) - 1 - friend_number - block_number
    #friendの要素数
    #print(friend.dfs_stack(i+1))
    #辞書での要素数
    #print(len(friend.adjacency_dict[i+1]))

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

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

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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

n, m, k = list(map(int, input().split()))
friend = [set() for i in range(n+1)]
block = [set() for i in range(n+1)]
tree = Union_Find(n)
for i in range(m):
    a, b = map(int, input().split())
    friend[a].add(b)
    friend[b].add(a)
    tree.union(a, b)

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

ans = []
for i in range(1, n+1):
    tree.find(i)

friend_list = [set() for i in range(n+1)]
for i in range(1, n+1):
    friend_list[tree.find(i)].add(i)
    """
for i in range(1, n+1):
    group = friend_list[tree.find(i)]
    group = group - friend[i] - block[i]
    ans.append(len(group)-1)
"""
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] 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)
	
for _ in range(K):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
	
# 同じ連結成分にラベルを振る（まだラベルを振っていない = -1 で初期化）
label = [-1] * N

cnt_label_num = 0

for i in range(N):
	if label[i] != -1: continue # もう振ってあったら飛ばす
	
	# 振ってなかったら幅優先でラベルを振る
	Q = [i]
	while Q:
		cur = Q.pop(0)
		if label[cur] != -1:
			label[cur] = cnt_label_num
		for adj in friend[cur]:
			if label[adj] != -1: continue
			label[adj] = cnt_label_num
			Q.append(adj)
	
	cnt_label_num += 1
	
# お友達候補計算
cnt = Counter(label)
for i in range(N):
	friend_candidate = cnt[label[i]] - 1 # 同じグラフにいる人
	friend_candidate -= len(friend[i]) # 元から友達を引く
	# blockしている人が同じグラフにいるときはその分引く
	for block_man in block[i]:
		if label[i] == label[block_man]:
			friend_candidate -= 1
	print(friend_candidate, end = " ")

Submission status: Wrong Answer

Solution code:
class Unionfind():

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

    def find(self,a):
        if self.parents[a]<0:
            return a
        else:
            self.parents[a]=self.find(self.parents[a])##事実上for文
            return self.parents[a]


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

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

    def same(self,x,y):
        if self.find(x)==self.find(y):
            return True
        else:
            return False
          
N,M,K=map(int,input().split())
uf=Unionfind(N)
friend=[list(map(int,input().split())) for i in range(M)]
block=[list(map(int,input().split())) for i in range(K)]
ff=[[] for i in range(N)]
bb=[[] for i in range(N)]
ans=[]
for i in range(M):
    uf.union(friend[i][0]-1,friend[i][1]-1)
    ff[friend[i][0]-1].append(friend[i][1]-1)
    ff[friend[i][1]-1].append(friend[i][0]-1)
for i in range(K):
    bb[block[i][0]-1].append(block[i][1]-1)
    bb[block[i][1]-1].append(block[i][0]-1)
for i in range(N):
    ans.append(uf.size(i)-1-(len(ff[i])))
    for j in bb[i]:
        if uf.same(j,i)==True:
            ans[i]-=1
print(ans)

Submission status: Wrong Answer

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

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

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].append(d)
    Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    l = [x for x in Frends[i] if x>i]
    if len(l) == 0:
        continue

    l.append(i)
    s = set(l)

    t = -1
    j = 0
    fglen = len(fg)
    while j < fglen:
        sfg = s&fg[j]
        if len(sfg) > 0:
            if t < 0:
                t = j
                fg[j] |= s
            else:
                fg[t] |= fg[j]
                fg.pop(j)
                fglen -= 1
        j += 1

    if t < 0:
        fg.append(s)

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for g in fg:
    for f in g:
        cand[f] = len(g)-len(Frends[f])-len(set(Blocked[f])&g)-1

# output
print(fg)
print(" ".join(map(str, cand)))

Submission status: Wrong Answer

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

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

from collections import deque
clusters=[]
visited=[0]*n
list_cluster=[0]*n
i_c=0

for i in range(n):
    if visited[i]==0:
        start=i
    else:
        continue

    cluster =[start]
    q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
    visited[start]=1
    list_cluster[start]=i_c
    
    while q:
        parent,x = q.popleft()
        for y in friend[x]:
            if visited[y]==0:
                q.append((x,y))#子ノードを追加
                visited[y]=1
                cluster.append(y)
                list_cluster[y]=i_c
    clusters.append(cluster)
    i_c+=1

ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
for f0,f1 in friends_pair:
    if list_cluster[f0] ==  list_cluster[f1]:
        ans[f0]-=1
        ans[f1]-=1
for b0,b1 in block:
    if list_cluster[b0] ==  list_cluster[b1]:
        ans[b0]-=1
        ans[b1]-=1
print(*ans)

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
f_p=[]
b_p=[]
fri_list=[]
bro_list=[]
for _ in range(M):
    f=list(map(int,input().split()))
    f[0]-=1;f[1]-=1
    f_p.append(f)
for _ in range(K):
    b=list(map(int,input().split()))
    b[0]-=1;b[1]-=1
    b_p.append(b)
for id in range(N):
    fri=[0]*N
    bro=[0]*N
    fri[id]=2
    bro[id]=2
    fri_list.append(fri)
    bro_list.append(bro)

for pair in f_p:
    fri_list[pair[0]][pair[1]]=1
    fri_list[pair[1]][pair[0]]=1

for pair in b_p:
    bro_list[pair[0]][pair[1]]=10
    bro_list[pair[1]][pair[0]]=10

for i in range(N):
    for k in range(N):
        if fri_list[i][k]==1:
            for j in range(N):
                if fri_list[i][j]==0 and fri_list[k][j]==1:
                    fri_list[i][j]=10

for i in range(N):
    for k in range(N):
        if fri_list[i][k]==10 and bro_list[i][k]==10:
            fri_list[i][k]=-1

ans=[]
for i in range(N):
    ans.append(fri_list[i].count(10))
print(" ".join(list(map(str,ans))))

Submission status: Wrong Answer

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

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

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].append(d)
    Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        if i > f:
            continue

        t = -1
        s = set([i, f])
        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            sand = s&g
            if t < 0:
                if len(sand) > 0:
                    t = j
                    if sand == s:
                        break
                    elif i in sand:
                        g.add(f)
                    else:
                        g.add(i)

            elif len(sand) > 0:
                #   同一人物を含む友人グループを結合
                fg[t] = fg[t] | g
                fg.pop(j)
                fglen -= 1
            
            j += 1

        if t < 0:
            fg.append(s)

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for i in range(N):
    for g in fg:
        if i in g:
            cand[i] = len(g)-len(Frends[i])-len(set(Blocked[i])&g)-1
            break

# output
print(fg)
print(" ".join(map(str, cand)))

Submission status: Wrong Answer

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

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

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].append(d)
    Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        if i > f:
            break

        t = -1
        s = set([i, f])
        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            sand = s&g
            if t < 0:
                if len(sand) > 0:
                    t = j
                    if sand == s:
                        break
                    elif i in sand:
                        g.add(f)
                    else:
                        g.add(i)

            elif len(sand) > 0:
                #   同一人物を含む友人グループを結合
                fg[t] = fg[t] | g
                fg.pop(j)
                fglen -= 1
            
            j += 1

        if t < 0:
            fg.append(s)

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for i in range(N):
    for g in fg:
        if i in g:
            cand[i] = len(g)-len(Frends[i])-len(set(Blocked[i])&g)-1
            break

# output
#print(fg)
print(" ".join(map(str, cand)))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

tb = [[None]*n for i in range(n)]
# 友達登録
for i in range(m):
    tb[fr[i][0]-1][fr[i][1]-1] = 1
    tb[fr[i][1]-1][fr[i][0]-1] = 1
# ブロック登録
for i in range(k):
    tb[br[i][0]-1][br[i][1]-1] = -1
    tb[br[i][1]-1][br[i][0]-1] = -1
# 自分は無視
for i in range(n):
    tb[i][i] = 0

#print("- - - - - - -")
#print(*tb, sep="\n")

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

    for i in range(n):
        #print("-- ",i+1,"の友達候補探し")
        #表の初期化
        g = [None for i in range(n)]

        stack = deque()
        stack.append(i)
        #最初の地点のコストは0
        g[i] = 0

        while stack:
            k = stack.pop() #stackから取り出す
            move = [d for d in range(n) if tb[k][d] == 1]#友達なら移動
            moveprint = [d+1 for d in range(n) if tb[k][d] == 1]
            #print(k+1, "の友達", moveprint)
            for dk in move:
                if g[dk] == None:
                    g[dk] = 1
                    stack.append(dk)
                    if tb[i][dk] == None:
                        #print(i+1,dk+1,"は友達！")
                        ans[i] += 1
                        ans[dk] += 1

    return ans

#友達を辿ってたどり着けるところまで考える
print(*dfs_check(), sep=" ")