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:
from collections import Counter

class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[-1 for i in range(n)]
        self.rank=[0]*(n)

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

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

        ##木の高さを比較し、低い方から高い方へ辺をはる
        if x==y:
          return

        if self.par[x]>self.par[y]:
          x,y=y,x
          
        self.par[x]+=self.par[y]
        self.par[y]=x

    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    def size(self,x):
      return -self.par[self.find(x)]
      
    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.par) if x<0]
    
    def all_group_member(self):
      return {r:self.members(r) for r in self.roots()}
      
n,m,k=map(int,input().split())
uf=union_find(n)
good=[0 for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  good[a-1]+=1
  good[b-1]+=1
  
  
ans=[0  for _ in range(n)]
    
    
bad=[0 for _ in range(n)]
for _ in range(k):
  p,q=map(int,input().split())
  if uf.same(p-1,q-1):
    
    bad[p-1]+=1
    bad[q-1]+=1


ans1=[]
for u in range(n):
  C=uf.size(u)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        # self.group_num = n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        # self.group_num -= 1

n, m, k = LI()
U = UnionFind(n)
G1 = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G1[a - 1] += [b - 1]
    G1[b - 1] += [a - 1]
    U.union(a - 1, b - 1)

G2 = [[] for _ in range(n)]
for _ in range(k):
    c, d = LI()
    G2[c - 1] += [d - 1]
    G2[d - 1] += [c - 1]

for i in range(n):
    print(U.get_size(i) - 1 - len(G1[i]) - len(G2[i]), end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        # self.group_num = n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        # self.group_num -= 1

n, m, k = LI()
U = UnionFind(n)
G1 = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G1[a - 1] += [b - 1]
    G1[b - 1] += [a - 1]
    U.union(a - 1, b - 1)

G2 = [[] for _ in range(n)]
for _ in range(k):
    c, d = LI()
    G2[c - 1] += [d - 1]
    G2[d - 1] += [c - 1]

for i in range(n):
    print(U.get_size(i) - 1 - len(G1[i]) - len(G2[i]), end="\t")

Submission status: Wrong Answer

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n,m,k = map(int,ipt().split())
    fl = [[] for i in range(n)]
    bl = [set() for i in range(n)]
    for i in range(m):
        a,b = map(int,ipt().split())
        fl[a-1].append(b-1)
        fl[b-1].append(a-1)
    for i in range(k):
        c,d = map(int,ipt().split())
        bl[c-1].add(d-1)
        bl[d-1].add(c-1)

    ans = [-1]*n
    al = [True]*n
    for i in range(n):
        if al[i]:
            q = [i]
            al[i] = False
            st = set([i])
            while q:
                qi = q.pop()
                for j in fl[qi]:
                    if al[j]:
                        st.add(j)
                        al[j] = False
                        q.append(j)
#            for j in st:
#                ans[j] = len(st-bl[j])-len(fl[j])-1

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


    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
    
n,m,k=map(int,input().split())
pair=[-1]*n

def main():
#    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
#    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

    ii=0        
    ss=size(ii)-len(g[ii])-len(x[ii])-1
    strs=""
    for i in range(n):
        ss=size(i)-1
        rooti=root(i)
        for gi in g[i]:
            if root(gi)==rooti:
                ss-=1
        for xi in x[i]:
            if root(xi)==rooti:
                ss-=1
#        strs=strs+" "+str(ss)
    print(strs[1:])
    
def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]


main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
    
n,m,k=map(int,input().split())
pair=[-1]*n

def main():
#    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
#    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

    ii=0        
    ss=size(ii)-len(g[ii])-len(x[ii])-1
    strs=""
    for i in range(1):
        ss=size(i)-1
        rooti=root(i)
        for gi in g[i]:
#            if root(gi)==rooti:
            ss-=1
        for xi in x[i]:
#            if root(xi)==rooti:
            ss-=1
        strs=strs+" "+str(ss)
    print(strs[1:])
    
def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]


main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
    
n,m,k=map(int,input().split())
pair=[-1]*n

def main():
#    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
#    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

    ii=0        
    ss=size(ii)-len(g[ii])-len(x[ii])-1
    strs=""
    for i in range(n):
        ss=size(i)-1
        rooti=root(i)
        for gi in g[i]:
#            if root(gi)==rooti:
            ss-=1
        for xi in x[i]:
#            if root(xi)==rooti:
            ss-=1
        strs=strs+" "+str(ss)
    print(strs[1:])
    
def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]


main()

Submission status: Wrong Answer

Solution code:
n,m,k=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().rstrip().split()]
  l[a-1].append(b-1)
  l[b-1].append(a-1)

block=[[] for i in range(n)]
done=[0 for i in range(n)]

ans=[0 for i in range(n)]
def bfs(i):
  cnt=0
  que=[i]
  if done[i]==0:
    while(que):
      now=que.pop(0)
      l.append(now)
      done[now]=i+1
      cnt+=1
      for j in l[now]:
        if done[j]==0:
          done[j]=i+1
          que.append(j)
    for s in range(n):
      if done[s]==i+1:
        ans[s]=cnt

for i in range(n):
  bfs(i)
  
for i in range(k):
  c,d=[int(x) for x in input().rstrip().split()]
  if ans[c-1]==ans[d-1]:
    block[c-1].append(d-1)
    block[d-1].append(c-1)

for i in range(n):
  ans[i]=ans[i]-(len(l[i])+len(block[i])+1)
print(*ans)

Submission status: Wrong Answer

Solution code:
def dijkstra(s, n, graph):
  INF = float('inf')
  min_dist = [INF] * n
  visited = [False] * n
  min_dist[s] = 0

  while True:
    next_visit = -1

    for i in range(n):
      if (not visited[i]) and (next_visit == -1):
        next_visit = i

      elif (not visited[i]) and min_dist[i] < min_dist[next_visit]:
        next_visit = i

    if next_visit == -1:
      break

    visited[next_visit] = True

    for j in range(n):
      min_dist[j] = min(min_dist[j], min_dist[next_visit] + graph[next_visit][j])
  return min_dist

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


adj1 = [[float('inf') for row in range(N)] for col in range(N)]
adj2 = [[float('inf') for row in range(N)] for col in range(N)]

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

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

res = []
for i in range(N):
  f = dijkstra(i, N, adj1)
  b = dijkstra(i, N, adj2)
  c = 0
  for j in range(N):
    if 1 < f[j] < N and N < b[j]:
      c += 1
  res.append(c)

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

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter
import sys

N_MAX = 100000 + 5
sys.setrecursionlimit(N_MAX)

N, M, K = map(int, sys.stdin.readline().rstrip().split())

fr = [[] for _ in range(N)]  # 友達関係
for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    fr[a - 1].append(b - 1)
    fr[b - 1].append(a - 1)

bl = [[] for _ in range(N)]  # ブロック関係
for _ in range(K):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    bl[a - 1].append(b - 1)
    bl[b - 1].append(a - 1)


gr = [0] * N  # 友達候補グループ


# ## BFS ## #
def bfs(u, num):

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()
        for v in fr[u]:
            if gr[v] == 0:  # state を確認
                gr[v] = num  # state を変更
                q.append(v)


num = 1
for i in range(N):
    if gr[i] == 0:
        bfs(i, num)
        num += 1

# print(gr)

gr_num = Counter(gr)  # グループの人数を数えておく


# グループの中から、友達でも
ans = []
for i in range(N):
    kouho_suu = gr_num[gr[i]]
    for f in fr[i]:
        if gr[i] == gr[f]:
            kouho_suu -= 1
    for b in bl[i]:
        if gr[i] == gr[b]:
            kouho_suu -= 1
    kouho_suu -= 1

    ans.append(kouho_suu)

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

N, M, K = map(int, sys.stdin.readline().rstrip().split())

fr = [[] for _ in range(N)]  # 友達関係
for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    fr[a - 1].append(b - 1)
    fr[b - 1].append(a - 1)

bl = [[] for _ in range(N)]  # ブロック関係
for _ in range(K):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    bl[a - 1].append(b - 1)
    bl[b - 1].append(a - 1)


# ## BFS ## #
def bfs(u, num):

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()
        for v in fr[u]:
            if gr[v] == 0:  # state を確認
                gr[v] = num  # state を変更
                q.append(v)


# 友達グループを探す
gr = [0] * N

num = 1
for i in range(N):
    if gr[i] == 0:
        bfs(i, num)
        num += 1

# グループの人数を数えておく
gr_num = Counter(gr)

# グループの中から、友達でも
kh = [[] for _ in range(N)]
for i in range(N):
    for j in range(i, N):
        if gr[i] == gr[j]:
            kh[i].append(j)
            kh[j].append(i)

ans = []
for i in range(N):
    ans.append(len(set(kh[i]) - set(fr[i]) - set(bl[i])) - 1)

print(*ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,n):
        self.root = list(range(n))
        self.size = [1] * (n)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx                                                                                                    
        else:
            self.root[y] = x
            self.size[x] += sy

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

uf = UnionFind(n)
ex = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.merge(a,b)
    ex[a].append(b)
    ex[b].append(a)

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.find_root(c) == uf.find_root(d):
        ex[c].append(d)
        ex[d].append(c)

ans = []
for i in range(n):
    ans.append(uf.size[uf.root[i]] - len(ex[i]) - 1)
ans = [str(i) for i in ans]
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,n):
        self.root = list(range(n))
        self.size = [1] * (n)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx                                                                                                    
        else:
            self.root[y] = x
            self.size[x] += sy

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

uf = UnionFind(n)
ex = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.merge(a,b)
    ex[a].append(b)
    ex[b].append(a)

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.find_root(c) == uf.find_root(d):
        ex[c].append(d)
        ex[d].append(c)

ans = []
for i in range(n):
    ans.append(uf.size[uf.root[i]] - len(list(set(ex[i]))) - 1)
ans = [str(i) for i in ans]
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,N):
        self.root = list(range(N+1))
        self.size = [1] * (N+1)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy

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

uf = UnionFind(n)
ex = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    uf.merge(a,b)
    ex[a].append(b)
    ex[b].append(a)

for i in range(k):
    c, d = map(int, input().split())
    if uf.find_root(c) == uf.find_root(d):
        ex[c].append(d)
        ex[d].append(c)

ans = []
for i in range(1, n+1):
    ans.append(uf.size[uf.root[i]] - len(list(set(ex[i]))) - 1)
ans = [str(i) for i in ans]
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

# N,M,K = [10,random.randint(1,10),random.randint(1,10)]

ad={} #友達関係
block={} #ブロック
for n in range(N):
    n=n+1
    ad[n]=set([])
    block[n]=set([])
    
for m in range(M):
    m1,m2 = list(map(int,input().split()))
    ad[m1].add(m2)
    ad[m2].add(m1)

for k in range(K):
    k1,k2 = list(map(int,input().split()))
    block[k1].add(k2)
    block[k2].add(k1)

visit = deque([])
color={}
tree={}
t=0
for n in range(N):
    n=n+1
    color[n] = -1
    tree[n] = -1
    
start_ = 1
    
while len(visit) < N:
    t += 1
    for c_k in range(start_,N):
        print(c_k)
        if color[c_k] == -1:
            start = c_k
            start_ = start + 1
            break
    color[start] = 0
    tree[start] = t
    visit_temp=deque([start])

    while len(visit_temp) > 0: #BFS
        start=visit_temp[0]
        for v in ad[start] :
            if color[v] == -1: #未訪問
                visit_temp.append(v)
                color[v] = 0
                
        color[start] = 1
        tree[start] = t
        
        pop_ = visit_temp.popleft()
        visit.append(pop_)
        
tree_={}
for v in set(tree.values()):
    tree_[v]=set()
    
for k in set(tree.keys()):
    tree_[tree[k]].add(k)
    
print(tree,tree_)
    
ans=[]
for n in range(N):
#     print('===')
    n=n+1
    
    tree_len=len(tree_[tree[n]])
    friend_len=len(ad[n])
    
    brock_len=0
    for b in block[n]:
        if tree[n] == tree[b]:
            brock_len += 1
            
#     print(tree_len,friend_len,brock_len)
#     print(tree_len-friend_len-brock_len-1)
    ans.append(tree_len-friend_len-brock_len-1)
            
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

ad={} #友達関係
block={} #ブロック
for n in range(N):
    n=n+1
    ad[n]=set([])
    block[n]=set([])
    
for m in range(M):
    m1,m2 = list(map(int,input().split()))
    ad[m1].add(m2)
    ad[m2].add(m1)
    
for k in range(K):
    print()

for k in range(K):
    k1,k2 = list(map(int,input().split()))
    block[k1].add(k2)
    block[k2].add(k1)

start = 1
next_start = start
visit = deque([])

color={}
tree={}
t=0
for n in range(N):
    n=n+1
    color[n] = -1
    tree[n] = -1
    
color[start]=0
tree[start]=t
    
while len(visit) < N:
    t += 1
    start = next_start
    visit_temp=deque([start])
#     print(start)

    while len(visit_temp) > 0: #BFS
        start=visit_temp[0]
        for v in ad[start] :
            if color[v] == -1: #未訪問
                visit_temp.append(v)
                color[v] = 0
                
        color[start] = 1
        tree[start] = t
        
        pop_ = visit_temp.popleft()
        if next_start == pop_:
            next_start += 1
        visit.append(pop_)
        

tree_={}
for v in set(tree.values()):
    tree_[v]=set()
    
for k in set(tree.keys()):
    tree_[tree[k]].add(k)
    
ans=[]
for n in range(N):
#     print('===')
    n=n+1
    
    tree_len=len(tree_[tree[n]])
    friend_len=len(ad[n])
    
    brock_len=0
    for b in block[n]:
        if tree[n] == tree[b]:
            brock_len += 1
            
#     print(tree_len,friend_len,brock_len)
#     print(tree_len-friend_len-brock_len-1)
    ans.append(tree_len-friend_len-brock_len-1)
            
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

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

n,m,k =map(int,input().split())# nは頂点の数、mは辺の数
g = [[] for _ in range(n)] # 隣接リスト
g_sub = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
for _ in range(k):
    c, d = [int(x) for x in input().split()]
    g_sub[c-1].append(d-1)
    g_sub[d-1].append(c-1)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d
answer=[]
for i in range(0,n):
    d=bfs(i)
    for j in range(len(g_sub[i])):
        d[g_sub[i][j]]="#"
    s=0
    for l in range(len(d)):
        if (d[l]!=None and d[l]!="#"):
            if d[l]>=2:
                s+=1
    answer.append(s)
print(answer)

Submission status: Wrong Answer

Solution code:
nmk=input("").split(" ")
n=int(nmk[0])
m=int(nmk[1])
k=int(nmk[2])
listin=[-1]*n
listf=[]
listb=[]
for i in range(n):
    listf+=[[]]
    listb+=[[]]
for i in range(m):
    ab=input("").split(" ")
    a=int(ab[0])-1
    b=int(ab[1])-1
    listf[a]+=[b]
    listf[b]+=[a]
for i in range(k):
    ab=input("").split(" ")
    a=int(ab[0])-1
    b=int(ab[1])-1
    listb[a]+=[b]
    listb[b]+=[a]
s=-1
listff=[]

for i in range(n):
    if(listin[i]==-1):
        s+=1
        listin[i]=s
        listff+=[[i]]
        cnt=0
        
        while(len(listff[s])>cnt):
            for ii in listf[listff[s][cnt]]:
                if(listin[ii]==-1):
                    listin[ii]=s
                    listff[s]+=[ii]
                    
            cnt+=1
listans=[]

for i in range(n):
    
    listans+=[str(len(set(listff[listin[i]]))-1-len(listf[i]))]
print(" ".join(listans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]
    
    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)
l,labels=connected_components(frends)
labels
labels=list(labels)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]
    
    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)
l,labels=connected_components(frends)
labels
labels=list(labels)

class Group:
    def __init__(self,labels):
        self.group=[np.array([0]*n) for i in range(l)]
        self.labels=labels
        self.group_num=[0 for i in range(l)]
        for i in labels:
            self.group_num[i]+=1
    def get_group_num(self,i):
        return self.group_num[self.labels[i]]

group=Group(labels)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]
    
    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)

Submission status: Wrong Answer

Solution code:
from collections import deque

def cou(i,abwk,cdwk,wk):
    an=0
    tz=deque([i])+wk
    cd=0
    while wk:
        wwk=deque()
        j=wk.pop()
        for k in abwk[j]:
            if k not in tz:
                if i in cdwk[k]:
                    cd+=1
                wwk.append(k)
                an+=1
                tz.append(k)
            else:
                continue
        wk=wwk
    return(an-cd)

n,m,k=map(int,input().split())
abwk=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    abwk[a].append(b)
    abwk[b].append(a)

cdwk=[[] for i in range(n+1)]
for i in range(k):
    c,d=map(int,input().split())
    cdwk[c].append(d)
    cdwk[d].append(c)

an=[0]*n

for i in range(1,n+1):
    wk=deque(abwk[i])
    if wk:
        an[i-1]=cou(i,abwk,cdwk,wk)
    else:
        continue

for i in an:
    print(i,end=' ')

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import connected_components

Submission status: Wrong Answer

Solution code:
def cou(i,abwk,cdwk,wk):
    an=0
    tz=[i]+wk
    while wk:
        wwk=[]
        for j in wk:
            for k in abwk[j]:
                if k not in tz and i not in cdwk[k]:
                    wwk.append(k)
                    an+=1
                    tz.append(k)
                else:
                    continue

        wk=wwk
    return(an)

n,m,k=map(int,input().split())
abwk=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    abwk[a].append(b)
    abwk[b].append(a)

cdwk=[[] for i in range(n+1)]
for i in range(k):
    c,d=map(int,input().split())
    cdwk[c].append(d)
    cdwk[d].append(c)

an=[0]*n

for i in range(1,n+1):
    if abwk[i]:
        an[i-1]=cou(i,abwk,cdwk,abwk[i])
    else:
        continue

for i in an:
    print(i,end=' ')