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 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
    for i in range(n):
        ans[i] =ans[i]//2

    return ans

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

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(i,n) if tb[k][d] == 1]#友達なら移動
            moveprint = [d+1 for d in range(i,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=" ")

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(i,n) if tb[k][d] == 1]#友達なら移動
            moveprint = [d+1 for d in range(i,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=" ")

Submission status: Wrong Answer

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

    def FindRoot(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.FindRoot(self.parents[x])
            return self.parents[x]
    
    def Union(self,x,y):
        x = self.FindRoot(x)
        y = self.FindRoot(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 isSame(self,x,y):
        return self.FindRoot(x) == self.FindRoot(y)

    def Size(self,x):
        return -self.parents[self.FindRoot(x)]

n,m,k = [int(x) for x in input().split()]
obj = UnionFind(n)
cnt = [0]*(n+1)
for _ in range(m):
    a,b = [int(x) for x in input().split()]
    obj.Union(a,b)
    cnt[a] += 1
    cnt[b] += 1
for _ in range(k):
    c,d = [int(x) for x in input().split()]
    cnt[c] += 1
    cnt[d] += 1
ans = 0
for i in range(1,n+1):
    ans = obj.Size(i)-1-cnt[i]
    print(ans,end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import time
n,m,k = map(int,input().split())
fr = defaultdict(set)
bl = []
start = time.time()
group = [0] * n

for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  fr[a].add(b)
  fr[b].add(a)

for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  bl.append((a,b))


g_num = 0
for i in range(n):
    if group[i] != 0:
        continue
    g_num += 1
    unvisited = set({i})
    while len(unvisited) > 0:
        v = unvisited.pop()
        group[v] = g_num
        for w in fr[v]:
            if group[w] > 0 or w in unvisited:
                continue
            unvisited.add(w)

group_size = defaultdict(int)
for x in group:
    group_size[x] += 1

bl_in_group = [0] * n
for a,b in bl:
    if group[a] == group[b]:
        bl_in_group[a] += 1
        bl_in_group[b] += 1

for i in range(n):
    print(group_size[group[i]] - len(fr[i]) - bl_in_group[i] - 1, end=' ')

print(group)

Submission status: Wrong Answer

Solution code:
'''
Created on 2020/03/04

@author: fanta
'''
import time
N,M,K = map(int, input().split())
friends_set = []
enemies_set = []
groups = []
menbers = set()
group_num = -1
bond = []
count = {}
results = {}

start = time.time()

for i in range(M):
    friends_set.append(set(int(x) for x in input().split()))

for i in range(K):
    enemies_set.append(set(int(x) for x in input().split()))

for n in range(N):
    results[n+1] = 0
    count[n+1] = 0

# print(time.time() - start)
# start2 = time.time()

for friend in friends_set:
    if friend.isdisjoint(menbers):
        group_num += 1
        groups.append(set(friend))

    else:
        for v in range(group_num+1):
            if (friend.isdisjoint(groups[v]))^True:
                groups[v] = groups[v] | friend
                bond.append(v)

            if len(bond) > 1:
                groups[bond[0]]= groups[bond[1]] | groups[bond[0]]
                groups[bond[1]].clear()
                group_num = len(groups) - 1
        bond.clear()
    menbers = menbers | friend

# print(time.time() - start2)
# start3 = time.time()

for v in range(group_num+1):
    for friend in friends_set:
        if friend <= groups[v]:
            friend_list = list(friend)
            count[friend_list[0]] += 1
            count[friend_list[1]] += 1
            break

    for enemy in enemies_set:
        if enemy <= groups[v]:
            enemy_list = list(enemy)
            count[enemy_list[0]] += 1
            count[enemy_list[1]] += 1
            break

    group_len = len(groups[v])
    for i in groups[v]:
        results[i] = group_len - 1 - count[i]

# print(time.time() - start3)


for out in results.values():
    print(out,end=' ')

Submission status: Wrong Answer

Solution code:
N , M , K = map(int, input().split())
Y_c = []
for i in range(N):
    Y_c.append(N-1)


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

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


print(" ".join([str(i) for i in Y_c]))

Submission status: Wrong Answer

Solution code:
#途中
N,M,K = map(int,input().split())
Fri = [list(map(int,input().split())) for _ in range(M)]
Blo = [list(map(int,input().split())) for _ in range(K)]
print(Fri)
print(Blo)

#union-find
par = [i for i in range(N+1)]
relation = [1 for _ in range(N+1)] #自身を含む同グループの数
rank = [0 for _ in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x,y = find(x),find(y)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
            relation[y] += relation[x]
        else:
            par[y] = x
            relation[x] += relation[y]
            if rank[x] == rank[y]:
                rank[x] += 1

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

ans = [relation[find(i)] for i in range(N+1)]
for m in range(M):
    unite(Fri[m][0],Fri[m][1])
    ans[Fri[m][0]] -= 1
    ans[Fri[m][1]] -= 1

for k in range(K):
    if same(Blo[k][0],Blo[k][1]):
        ans[Blo[k][0]] -= 1
        ans[Blo[k][1]] -= 1

for i in range(1,N+1):
    ans[i] += (relation[find(i)] - 2)
    if i != 1:
        print(" ",end="")
    print(ans[i],end="")

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline

    N, M, K=map(int, input().split())
    friend_or_block = [set()] * N
    friends_chain = UnionFindTree(N)

    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        friends_chain.union(a, b)
        friend_or_block[a].add(b)
        friend_or_block[b].add(a)

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c].add(d)
            friend_or_block[d].add(c)

    print(*[friends_chain.size(i) - len(friend_or_block[i]) - 1 for i in range(N)])

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

par = [n+1 for n in range(N)]
rank = [0 for _ in range(N)]
size = [1 for _ in range(N)]

# 木の根を求める
def find(x):
  if par[x-1] != x:
    par[x-1] = find(par[x-1])
  return par[x-1]
# x, y の属する集合を併合
def unite(x, y):
  rx = find(x)
  ry = find(y)
  if rx == ry:
    return
  if rank[rx-1] < rank[ry-1]:
    rx, ry = ry, rx
  par[ry-1] = rx
  size[rx-1] += size[ry-1]
  if rank[rx-1] == rank[ry-1]:
    rank[rx-1] += 1
# x, y が同じ集合に属するか否か
def same(x, y):
  return find(x) == find(y)
def getsize(x):
  return size[find(x)-1]

friends = [0 for _ in range(N)]
for A, B in AB:
  unite(A, B)
  friends[A-1] += 1
  friends[B-1] += 1

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

for n in range(N):
  ans[n] = getsize(n+1) - friends[n] -1

for C, D in CD:
  if same(C, D):
    ans[C-1] -= 1
    ans[D-1] -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())


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 = UnionFind(N)

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

out = []
for x in range(N):
    out.append(uf.size(x)-1)
    # print(uf.size(x))

for x in ab:
    out[x[0] - 1] -= 1
    out[x[1] - 1] -= 1

cd = []
for _ in range(K):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        out[c - 1] -= 1
        out[d - 1] -= 1
print(out)

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

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

# print(friend_dict)
# print(block_dict)

visited = [] # Array to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        visited.append(node)
        # print(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

memory = {}

for k in range(1, n + 1):
    # Driver Code
    visited = []
    res = 0
    if k in memory:
        res = memory[k]
    else:
        dfs(visited, friend_dict, k)
        res = len(visited)
        for v in visited:
            memory[v] = res
    # res = len(visited) - 1
    res -= len(friend_dict[k])
    # print(visited)
    # print(block_dict[k])
    # print(set(visited).intersection(set(block_dict[k])))
    # res -= len(set(visited).intersection(set(block_dict[k])))
    print(str(res), end = ' ')

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

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

# print(friend_dict)
# print(block_dict)

visited = [] # Array to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        visited.append(node)
        # print(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

memory = {}

for k in range(1, n + 1):
    # Driver Code
    visited = []
    if k in memory:
        visited = memory[k]
    else:
        dfs(visited, friend_dict, k)
        for v in visited:
            memory[v] = visited
    res = len(visited) - 1
    res -= len(friend_dict[k])
    # print(visited)
    # print(block_dict[k])
    # print(set(visited).intersection(set(block_dict[k])))
    # res -= len(set(visited).intersection(set(block_dict[k])))
    print(str(res), end = ' ')

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

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

# print(friend_dict)
# print(block_dict)

visited = [] # Array to keep track of visited nodes.
# 
# def dfs(visited, graph, node):
#     if node not in visited:
#         visited.append(node)
#         # print(node)
#         for neighbour in graph[node]:
#             dfs(visited, graph, neighbour)
# 
# memory = {}
# 
# for k in range(1, n + 1):
#     # Driver Code
#     visited = []
#     if k in memory:
#         visited = memory[k]
#     else:
#         dfs(visited, friend_dict, k)
#         for v in visited:
#             memory[v] = visited
#     res = len(visited) - 1
#     res -= len(friend_dict[k])
#     # print(visited)
#     # print(block_dict[k])
#     # print(set(visited).intersection(set(block_dict[k])))
#     res -= len(set(visited).intersection(set(block_dict[k])))
#     print(str(res), end = ' ')

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(1500000000)

from collections import defaultdict

friend_dict = defaultdict(list)

block_dict = defaultdict(list)

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

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

# print(friend_dict)
# print(block_dict)

visited = [] # Array to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        visited.append(node)
        # print(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

memory = {}

for k in range(1, n + 1):
    # Driver Code
    visited = []
    if k in memory:
        visited = memory[k]
    else:
        # dfs(visited, friend_dict, k)
        for v in visited:
            memory[v] = visited
    res = len(visited) - 1
    res -= len(friend_dict[k])
    # print(visited)
    # print(block_dict[k])
    # print(set(visited).intersection(set(block_dict[k])))
    res -= len(set(visited).intersection(set(block_dict[k])))
    print(str(res), end = ' ')

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    for f in fl:
        if i+1 in f:
            isContinue = True
            break
    if isContinue:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        new_fl = p[r-1]['T']
        for nf in new_fl:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    for f in fl:
        if i+1 in f:
            for s in f:
                if not s in [i+1]+ dt['T'] + dt['B']:
                    ans[i] += 1
                    break

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

Submission status: Wrong Answer

Solution code:
import queue
q = queue.Queue()
n, m, k = map(int, input().split())
friend = [list(map(int, input().split())) for i in range(m)]
block = [list(map(int, input().split())) for i in range(k)]
suggestions = [] #友達候補
def Strand(now): #繋がり検索
    for o in range(m):
        if friend[o][0] == now:
            if friend[o][1] not in Q:
                q.put(friend[o][1])
                Q.append(friend[o][1])
        if friend[o][1] == now:
            if friend[o][0] not in Q:
                q.put(friend[o][0])
                Q.append(friend[o][0])

for i in range(n):
    now = i #現在地
    count = 0
    Q = [i] #発見済み
    Strand(i)

    F = [] #人iのフレンドリスト
    for j in range(m):
        if friend[j][0] == i:
            F.append(friend[j][1])
        if friend[j][1] == i:
            F.append(friend[j][0])
    B = [] #人iのブロックリスト
    for l in range(k):
        if block[l][0] == i:
            B.append(block[l][1])
        if block[l][1] == i:
            B.append(block[l][0])

    while not q.empty():
        if i != 0:
            for o in range(m):
                if friend[o][0] == now:
                    if friend[o][1] not in Q:
                        q.put(friend[o][1])
                        Q.append(friend[o][1])
                if friend[o][1] == now:
                    if friend[o][0] not in Q:
                        q.put(friend[o][0])
                        Q.append(friend[o][0])
        now = q.get()
        if (now not in F) and (now not in B):
            count += 1
    suggestions.append(count)

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

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    for f in fl:
        if i+1 in f:
            isContinue = True
            break
    if isContinue:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        tmp_fl = list(set(tmp_fl + p[r-1]['T']))
        rmn = list(set(rmn + list(set(p[r-1]['T']) - set(alr))))
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    l = [i+1]+ dt['T'] + dt['B']
    for f in fl:
        ans[i] = len(list(set(f) - set(l)))
            

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
linkList = []
ans = []
visited = [0] * (N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = [i]
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if j in f[n] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.append(j)
    linkList.append(link)

print(-1)

# for i in range(1,N+1):
#     #連結成分のサイズ
#     linkSize = 0
#     #「友達関係」または「ブロック関係」はマイナスする
#     minus = 0
#     for link in linkList:
#         if not i in link:
#             continue
#         for j in link:
#             linkSize = len(link)
#             if i in f[j] or i in b[j]:
#                 minus += 1
#     ans.append(linkSize-minus-1)
 
# print(*ans)

Submission status: Wrong Answer

Solution code:
#This class represents a undirected graph using adjacency list representation 
class UF:
    """An implementation of union find data structure.
    It uses weighted quick union by rank with path compression.
    """

    def __init__(self, N):
        """Initialize an empty union find object with N items.

        Args:
            N: Number of items in the union find object.
        """

        self._id = list(range(N))
        self._count = N
        self._rank = [0] * N

    def find(self, p):
        """Find the set identifier for the item p."""

        id = self._id
        while p != id[p]:
            p = id[p] = id[id[p]]   # Path compression using halving.
        return p

    def count(self):
        """Return the number of items."""

        return self._count

    def connected(self, p, q):
        """Check if the items p and q are on the same set or not."""

        return self.find(p) == self.find(q)

    def union(self, p, q):
        """Combine sets containing p and q into a single set."""

        id = self._id
        rank = self._rank

        i = self.find(p)
        j = self.find(q)
        if i == j:
            return

        self._count -= 1
        if rank[i] < rank[j]:
            id[i] = j
        elif rank[i] > rank[j]:
            id[j] = i
        else:
            id[j] = i
            rank[i] += 1

    def __str__(self):
        """String representation of the union find object."""
        return " ".join([str(x) for x in self._id])

    def __repr__(self):
        """Representation of the union find object."""
        return "UF(" + str(self) + ")"


n, m, k = [int(i) for i in input().split()]
g = UF(n)
friend = []
block = []
for i in range(m):
    friend.append([int(i)-1 for i in input().split()])
    g.union(friend[-1][0], friend[-1][1])
for i in range(k):
    block.append([int(i)-1 for i in input().split()])

repr_u  = [g.find(i) for i in range(n)]
potentialsize = [sum([1 for j in range(n) if repr_u[j] == repr_u[i] and [i,j] not in friend and [j,i] not in friend and 
    [i,j] not in block and [j,i] not in block])-1 for i in range(n)]
print(*potentialsize)

Submission status: Wrong Answer

Solution code:
# c0->c1->c2->...cLについて隣同士が全て友達関係なるようなc0~cLがあれば，c0->cLが友達候補になる

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

# 原理的にはiについてA[x]==i and not B[x]==i となるxを全て取り出してきてB[x]について，また同様に繰り返していくその時のCがiでなければ友人候補として加えるみたいな？
# でもそんなiterationと場合分けを繰り返していたらどう考えても時間内に終わらない．けど一応やってみるか
# エージェント毎にじゃなくて繋がり毎に計算すればよいかも
# とりあえず，友達関係について繰り返してみる．
# 1.友達関係から一つの関係(a,b)をpopする．(a,b)のa,bについてそれぞれ友達関係が繋がる場合は全てつなげていき．

# 以下正しい解き方
# 人を頂点，ともだちかんけいを辺とした無向グラフを作る．人iに対する答えは，
# (頂点iの連結成分のサイズ) - (頂点iと頂点jが同じ連結成分に含まれているようなjの数) - 1(自分自身)

# ここまではなんとなく理解していたとおりだがこれを高速化するには，各人が属する連結成分を求め，各連結成分の大きさを予め計算しておけばよい
# 深さ優先探索(DFSという)もしくはUnion-Findを使うことで高速化できる．

# これはいい感じのコードをパクってきた．
class UnionFind(object):
    __slots__ = ['nodes']

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

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            # 再帰的に親を探していくし更にノードの値を根の値にすべて更新する
            self.nodes[x] = self.find(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> bool:
        root_x, root_y, nodes = self.find(x), self.find(y), self.nodes
        # 根が違えばuniteを行い，
        if root_x != root_y:
            if nodes[root_x] > nodes[root_y]:
                root_x, root_y = root_y, root_x # 根を入れ替える，つまりroot_x<root_yとなる
            nodes[root_x] += nodes[root_y] #
            nodes[root_y] = nodes[root_x]
            return root_x != root_y

uf = UnionFind(N)
friend = [0] * N
block = [0] * N
for a, b in (map(int, input().split()) for _ in range(M)):
    uf.unite(a-1, b-1)
    friend[a-1] += 1
    friend[b-1] += 1

for c, d in (map(int, input().split()) for _ in range(K)):
    if uf.find(c-1) == uf.find(d-1):
        block[c-1] += 1
        block[d-1] += 1
ans = [-uf.nodes[uf.find(i)] - friend[i] -block[i] - 1 for i in range(N)]

print(*ans)

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 UnionFind():
    def __init__(self,n):
        self.n=[-1]*n
        self.r=[0]*n
    def Find_Root(self,x):
        if self.n[x]<0:
            return x
        else:
            self.n[x]=self.Find_Root(self.n[x])
            return self.n[x]
    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.r[x]>self.r[y]:
            self.n[x]+=self.n[y]
            self.n[y]=x
        else:
            self.n[y]+=self.n[x]
            self.n[x]=y
            if self.r[x]==self.r[y]:
                self.r[y]+=1
    def Root_Same(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)
    def Count(self,x):
        return -self.n[self.Find_Root(x)]
u=UnionFind(n)
for a,b in ab:
    u.Unite(a-1,b-1)
ans=[u.Count(i)-i for i in range(n)]
for a,b in ab:
    if u.Root_Same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1
for c,d in cd:
    if u.Root_Same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
print(*ans)