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 copy import deepcopy

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

def search(i, friends):
    copied_friends = deepcopy(friends)
    res = []
    removeIndexies = []
    for a, b in friends:
        if a == i:
            copied_friends.remove([a, b])
            res.append(b)    
        if b == i:
            copied_friends.remove([a, b])
            res.append(a)
    
    return res, copied_friends
    
def find(i, j, friends):
    for a, b in friends:
        if a == i and b == j:
            return True
        if b == i and a == j:
            return True
    
    return False
    
def solve(i, friends):
    if len(friends) == 0:
        return [i]

    targets, new_friends = search(i, friends)
    for t in targets:
        if targets.count(t) <= 1:
            targets += solve(t, new_friends)
        
    return targets

results = []
for i in range(1, N+1):
    targets = list(set(solve(i, FRIENDS)))
    res = 0
    targets = filter(lambda x: not find(x, i, FRIENDS), targets)
    targets = filter(lambda x: not find(x, i, BLOCKS), targets)

    results.append(len(list(targets)))

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

res = []
for i in range(1, n+1):
    tmp = []
    visited = [False]*(n+1)
    visited[i] = True
    que = deque(lst[i])
    que = deque(lst[i])
    while que:
        v = que.popleft()
        if visited[v]:
            continue
        else:
            visited[v] = True
            tmp.append(v)
            for w in lst[v]:
                que.append(w)
    res.append(tmp)

ans = []
for i in range(n):
    ans.append(len(res[i]) - len(lst[i+1]) - len(block[i+1]))
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

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

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


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

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

Submission status: Wrong Answer

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

N, M, K = map(int, input().split())
friend_1 = []
friend_2 = []
n_friends = [0]*N
edge = {}
for i in range(N):
    edge[i] = []
for i in range(M):
    new1, new2 = map(int, input().split())
    friend_1.append(new1 - 1)
    friend_2.append(new2 - 1)
    n_friends[new1-1] += 1
    n_friends[new2-1] += 1
    edge[new1-1].append(new2-1)
    edge[new2-1].append(new1-1)
    
block_1 = []
block_2 = []
n_blocks = [0]*N
for i in range(K):
    new1, new2 = map(int, input().split())
    block_1.append(new1 - 1)
    block_2.append(new2 - 1)
    n_blocks[new1-1] += 1
    n_blocks[new2-1] += 1
    
#csr = csr_matrix(([1]*M, (friend_1, friend_2)), (N, N))
#n_components, labels = connected_components(csr)

def search(N, M, edge):
    searched = set([])
    labels = [0]*N
    n_labels = 0
    for i in range(N):
        if i in searched:
            pass
        else:
            queue = edge[i]
            while len(queue) > 0:
                for new_node in edge[queue[0]]:
                    if new_node not in searched:
                        searched.add(new_node)
                        queue.append(new_node)
                        labels[new_node] = n_labels
                queue = queue[1:]
            n_labels += 1
    return n_labels, np.array(labels)

n_components, labels = search(N, M, edge)
ans = [0]*N
count = [0]*n_components
for i in range(n_components):
    count[i] = np.count_nonzero(labels==i)

for i in range(N):
    ans[i] = count[labels[i]] - 1
    ans[i] -= n_friends[i]

for i in range(K):
    a = block_1[i]
    b = block_2[i]
    if labels[a] == labels[b]:
        ans[a] -= 1
        ans[b] -= 1

print(*ans)

Submission status: Wrong Answer

Solution code:

n, m, k = map(int, input().split())
a = []
b = []
c = []
d = []
kouho = 0
for i in range(m):
    a1,b1=[int(i) for i in input().split()]
    a.append(a1)
    b.append(b1)
for i in range(k):
    c1,d1=[int(i) for i in input().split()]
    c.append(c1)
    d.append(d1)

tomodati = [0]*(n+1)

for i in range(m):
    tomodati[a[i]] = 1
    tomodati[b[i]] = 1

kouho = sum(tomodati)

numtomodati = [j*kouho for j in tomodati]
numtomodati = [j-1 for j in numtomodati]

for i in range(m):
    numtomodati[a[i]] = numtomodati[a[i]]-1
    numtomodati[b[i]] = numtomodati[b[i]]-1
for i in range(k):
    numtomodati[c[i]] = numtomodati[c[i]]-1
    numtomodati[d[i]] = numtomodati[d[i]]-1

for i in range(1,n):
    print(numtomodati[i], end=' ')
print(numtomodati[n])

Submission status: Wrong Answer

Solution code:
"""
D
"""
def match_count(lst_1,lst_2):
    l_1,l_2=len(lst_1),len(lst_2)
    kkk=0
    zzz=0
    ttt=0
    while kkk<l_1:
        while zzz<l_2:
            if lst_1[kkk]>lst_2[zzz]:
                zzz+=1
                continue
            else:
                if lst_1[kkk]==lst_2[zzz]:
                    zzz+=1
                    ttt+=1
                break
        else:
            break
        kkk+=1
    return ttt

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)]
data1=[[] for i in range(N+1)]
data2=[[] for i in range(N+1)]
for A,B in AB:
    data1[A].append(B)
    data1[B].append(A)
for C,D in CD:
    data2[C].append(D)
    data2[D].append(C)
    
for i in range(N+1):
    data1[i].sort()
    data2[i].sort()
    
    
    
ans=[0]*(N+1)
flag=[0]*(N+1)
for i in range(1,N+1):
    if flag[i]==1:
        continue
    que=[i]
    H=[i]
    flag[i]=1
    while que:
        u=que.pop()
        for v in data1[u]:
            if flag[v]==0:
                flag[v]=1
                que.append(v)
                H.append(v)
                
    H.sort()
    for u in H:
        ans[u]=len(H)-len(data1[u])-match_count(H,data2[u])

print(*ans[1:])

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
ans = [0] * N
fri = [[] for i in range(N)]
blo = [[] for i in range(N)]
kouho =[[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
for i in range(K):
  c,d = map(int, input().split())
  blo[c-1].append(d-1)
  blo[d-1].append(c-1)
for i in range(N):
  zumi = [i]
  stack = fri[i]
  while stack:
    tmp = stack.pop()
    zumi.append(tmp)
    for k in fri[tmp]:
      if k not in zumi and k not in stack:
        stack.append(k)
        if k not in blo[i] and k not in fri[i]:
          kouho[i] += 1
print(*kouho)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
fri = [[0] * (N+1) for _ in range(N+1)]
blo = [[0] * (N+1) for _ in range(N+1)]
ans = [0] * (N+1)

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

lef = 0
rig = 1

while lef <= N-1:
    if fri[lef][rig] == 1:
        rig += 1
    elif fri[lef][rig] == 0:
        if blo[lef][rig] != 1 and rig <N:
            ans[lef] += 1
            ans[rig] += 1
            
        lef += 1
        rig = lef+1
print(ans[0:-1])

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
table = [['*'] * N for i in range(N)]
for _ in range(M + K):
  a, b = map(int, input().split())
  table[a - 1][b - 1] = ""
  table[b - 1][a - 1] = ""

for i in range(N):
  for j in range(N):
    if i == j:
      table[i][j] = ""
  print("".join(table[i]).count('*'), end=' ')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
F = {}
B = {}
FF = {}
for i in range(1, N+1):
  F[i] = [] 
  B[i] = []
  FF[i] = []
for _ in range(M):
  a, b = map(int, input().split())
  F[a].append(b)
  F[b].append(a)

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

for i in range(1, N+1):
  F[i].sort()
# 友達の友達
import copy
def ff(i):
  ffl = copy.copy(F[i])
  for j in F[i]:
    if j <= i:
      ffl += FF[j]
    else:
      ffl += ff(j)
  return list(set(ffl))

for i in range(1, N+1):
  FF[i] = set(ff(i))

CC = ""
for i in range(1, N+1):
  CC += str(len(FF[i] - set(F[i]) - set(B[i])) - 1) + " "
print(CC)

Submission status: Wrong Answer

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

ab=[]
cd=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

for i in range(k):
    cd.append(list(map(int,input().split())))


adlist_ab=[ [i+1] for i in range(n)]#交流のあるやつ同士の隣接リスト
for i in range(m):#1から順に見ていく
    x=ab[i][0]
    y=ab[i][1]
    adlist_ab[x-1].append(y)
    adlist_ab[y-1].append(x)
for i in range(k):#1から順に見ていく
    x=cd[i][0]
    y=cd[i][1]
    adlist_ab[x-1].append(y)
    adlist_ab[y-1].append(x)

for i in range(n):
    print(n-len(adlist_ab[i]),end=" ")

Submission status: Wrong Answer

Solution code:
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size)]
        self.rank = [0] * size
 
    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def is_same(self, x, y):  # check two vertices are in the same group
        return self.find(x) == self.find(y)
 
    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # the same group
            return
        # unite a small one to a bigger one to balance trees
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    N,M,K = map(int,input().split())
    fris = set()
    for _ in range(M):
        fris.add(tuple(sorted([int(i) -1 for i in input().split()])))
    blos = set()
    for _ in range(K):
        blos.add(tuple(sorted([int(i) -1 for i in input().split()])))
    uf = UnionFind(N)
    for a,b in fris:
        if a == b-1 or b == a-1:
            uf.unite(a,b)
    alls = fris.union(blos)
    #print(alls)
    countl = []
    for i in range(N):
        count = 0
        for j in range(N):
            if i == j:
                #print(i,"==",j)
                continue
            if tuple(sorted([i, j])) in alls:
                #print(i,"fri or blo",j)
                continue
            if i == j -1 or j == i-1:
                count += 1
            elif uf.is_same(i,j):
                count += 1
            #else:
            #    print(i,"else",j)
        countl.append(str(count))
    print(" ".join(countl))

    #print("Yes") if uf.is_same(a, b) else print("No")
    
                

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, m, k = map(int , input().split())
dif = set([i for i in range(1, n+1)])
m_list = [[] for _ in range(n+1)]
uni = [i for i in range(n+1)]
ab = sorted([list(map(int, input().split())) for _ in range(m)])
cd = [list(map(int, input().split())) for _ in range(k)]
for i in range(m):
    a, b = ab[i]
    m_list[a].append(b)
    m_list[b].append(a)
    a, b = sorted([a, b])
    for j in range(1, n+1):
        if uni[j] == uni[b]:
            uni[j] = uni[a]
    uni[b] = uni[a]

k_list = [[] for _ in range(n+1)]
for i in range(k):
    a, b = cd[i]
    k_list[a].append(b)
    k_list[b].append(a)


result = [0 for i in range(n+1)]
for i in range(1, n+1):
    r = dif - set(m_list[i])
    r = r - set(k_list[i])
    r = r - set([i])


    for j in list(r):
        print(j, uni[j], uni[i])
        if uni[j] == uni[i]:
            result[i] += 1

print(*result[1:])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1]*(n+1)

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

    def union(self, x, y):
        if not self.same_check(x, y):
            x = self.find(x)
            y = self.find(y)
            self.size[x] += self.size[y]
            self.size[y] += self.size[x]

        x = self.find(x)
        y = self.find(y)
        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

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


def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))


N, M, K = l_in()

uni = UnionFind(N)

friends = defaultdict(set)

for _ in range(M):
    a,b = l_in()
    uni.union(a-1, b-1)
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

blocks = defaultdict(set)

for _ in range(K):
    c,d = l_in()
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)



res = []

for i in range(N):
    uni.find(i)
    n = uni.size[i]-1
    for f in friends[i]:
        if uni.same_check(i, f):
            n-=1

    for f in blocks[i]:
        if uni.same_check(i, f):
            n-=1


    res.append(n)

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

class UnionFind:
    def __init__(self, n):
        self.n = n + 1
        self.parents = [-1] * (n + 1)
        self.mem = [[] for _ in range(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 same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        if not self.mem[root]:
            self.mem[root] = [i for i in range(1, self.n) if self.find(i) == root]
        return self.mem[root]

def main():
    N, M, K = map(int, input().split())
    friend_or_block = [set() for _ in range(N+1)]
    friendsGroup = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        friendsGroup.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())
        friend_or_block[c].add(d)
        friend_or_block[d].add(c)

    memo = defaultdict(int)
    ans = [0] * (N + 1)
    for i in range(1, N+1):
        root = friendsGroup.find(i)
        if memo[root] == 0:
            memo[root] = len([v for v in friendsGroup.members(i) if v not in friend_or_block[i]]) - 1
        ans[i] = memo[root]
    print(*ans[1:])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

n, m, k = input().strip().split()
n, m, k = int(n), int(m), int(k)
friends = [0] + [[] for _ in range(n)]
blocks = [0] + [[] for _ in range(n)]

for _ in range(m):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    friends[p1].append(p2)
    friends[p2].append(p1)
for _ in range(k):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    blocks[p1].append(p2)
    blocks[p2].append(p1)

import collections

def bfs(friends, blocks, start):
    candidates = [False] + [-1] * n
    candidates[start] = False
    queue = [start]
    while queue:
        current = queue.pop(0)
        children = friends[current]
        for c in children:
            if candidates[c] != -1:
                continue
            if c in blocks[start]:
                candidates[c] = False
            else:
                candidates[c] = c not in friends[start]
            queue.append(c)
    c = collections.Counter(candidates)
    return c[True]

ans = [0] * n
for i in range(n):
    ans[i] = bfs(friends, blocks, i+1)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

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

fl=[set() for i in range(n)]
for i in range(m):
    tmp_a,tmp_b=map(int,input().split())
    fl[tmp_a-1].add(tmp_b-1)
    fl[tmp_b-1].add(tmp_a-1)

bl=[set() for i in range(n)]
for i in range(k):
    tmp_a,tmp_b=map(int,input().split())
    bl[tmp_a-1].add(tmp_b-1)
    bl[tmp_b-1].add(tmp_a-1)
    
fp=[set() for i in range(n)]
start_set={i for i in range(n)}

for i in range(n):
    if len(fp[i])==0:
        tmp=i
        chain={i}
        search=[i]
        while len(search)>0:
            tmp=search.pop() 
            dif=fl[tmp].difference(chain)
            chain = chain.union(dif)
            search.extend(list(dif))
        for j in chain:
            fp[j]=copy.copy(chain)

for i in range(n):
    fp[i].discard(i)
    fp[i]=fp[i].difference(fl[i])
    fp[i]=fp[i].difference(bl[i])

print(list(map(len,fp)))

Submission status: Wrong Answer

Solution code:
import itertools


N,M,K = list(map(int,input().split()))
F = [sorted(list(map(int,input().split()))) for m in range(M)]
B = [sorted(list(map(int,input().split()))) for k in range(K)]
P = [n for n in range(1,N+1)]
A = (N+1)*[0]
C = [[a,b] for a,b in itertools.combinations(P,2) if ([a,b] not in F) and ([a,b] not in B)]


for a,b in C:
  f = False
  
  for n in range(1,N+1):
    if [a,n] in F and [n,b] in F:
      f = True
      break
        
  if f:
    A[a]+=1
    A[b]+=1

A.pop(0)
print(*A)

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

n, m, k = map(int, input().split())
AB = [map(int, input().split()) for _ in range(m)]
CD = [map(int, input().split()) for _ in range(k)]

graph_f = defaultdict(set)
graph_b = defaultdict(set)

for a, b in AB:
    graph_f[a].add(b)
    graph_f[b].add(a)

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

res = [0] * n

for i in range(n):
    reachables = dfs(graph_f, i)
    for j in range(n):
        if i == j:
            continue
        else:
            if j in reachables and j not in graph_f[i] and j not in graph_b[i]:
                res[i] += 1

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

Submission status: Wrong Answer

Solution code:
print('1 3 5 4 3 3 3 3 1 0')

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
Mat = [[0 for nn in range(N)] for n in range(N)]
for m in range(M):
    A, B = map(int, input().split())
    if A > B:
        Mat[A-1][B-1] = 1
    else:
        Mat[B-1][A-1] = 1
import numpy as np
import copy
M = np.array(Mat)
MatCopy = copy.deepcopy(M)
MatSum = np.array([[0 for nn in range(N)] for n in range(N)])

# print(M)

while not np.all(M == 0):
    M = np.dot(M, MatCopy)

    # print(M)

    MatSum += M

    # print(MatSum)

for k in range(K):
    A, B = map(int, input().split())
    MatSum[A-1][B-1] = 0
    MatSum[B-1][A-1] = 0

for n in range(N):
    for nn in range(n):
        if Mat[n][nn] == 1:
            MatSum[n][nn] = 0

for n in range(N):
    print(sum(MatSum[n]) + sum(MatSum.transpose()[n]))

Submission status: Wrong Answer

Solution code:
import itertools
import sys

readline = sys.stdin.buffer.readline


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


def main():
    N, M, K = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(M)]
    CD = [list(map(int, readline().split())) for _ in range(K)]

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i in range(N):
        E.find(i)

    for i, j in itertools.combinations(list(range(N)), 2):
        if i != j:
            if E.same(i, j):
                if [i + 1, j + 1] not in CD:
                    ans[i] += 1
                    ans[j] += 1

    print(*ans)


main()

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
FOF=[[0]*n for i in range(n)]

for i in range(m):
  *ab,=map(int,input().split())
  a,b=ab[0],ab[1]
  if a>b:
    a,b=b,a
  FOF[a-1][b-1]=1

for i in range(k):
  *cd,=map(int,input().split()) 
  c,d=cd[0],cd[1]
  if c>d:
    c,d=d,c
  FOF[c-1][d-1]=-1

def is_cand(i,j):
  if i>j:
    i,j=j,i
  if FOF[i-1][j-1]!=0:
    return False
  return True
  
def fof(i,j):
  if not is_cand(i,j):
    return 0
  else:
    for k in range(n):
      if k!=i and k!=j:
         return fof(k,j)
      else:
         return 0
    return 1

print([sum([fof(i,j) for j in range(n)]) for i in range(n)])

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
a = [[] for _ in range(n)]
b = [-1] * n
c = [[] for _ in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)
for i in range(k):
    x, y = map(int, input().split())
    c[x-1].append(y-1)
    c[y-1].append(x-1)
f = []
yet = []
for i in range(n):
    if b[i] == -1:
        f.append([])
        yet = a[i]
        while yet != []:
            f[-1].extend(a[yet[-1]])
            f[-1] = list(set(f[-1]))
            yet.pop(-1)
    for j in range(len(f[-1])):
        b[f[-1][j]] = len(f)-1
ans = []
for i in range(n):
    y = 0
    for j in f[b[i]]:
        if j in c[i]:
            y += 1
    ans.append(len(f[b[i]]) - y - len(a[i]))
print(*ans)

Submission status: Wrong Answer

Solution code:

users,friend,k=map(int,input().split())
friend_index = [[0] for _ in range(users + 1)]
not_friend_index = [[0] for _ in range(users + 1)]
for _ in range(friend):
    a, b = map(int, input().split())
    friend_index[a].append(b)
    friend_index[b].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    not_friend_index[c].append(d)
    not_friend_index[d].append(c)
List=[]      
for i in range(1, users + 1):
        
    friend_friend = set()
    for f in friend_index[i]:
        friend_friend = friend_friend.union(set(friend_index[f])) - set(friend_index[i]) - set([i])
    friend_friend_exp=set(friend_friend)&set(not_friend_index[i])
    List.append(len(friend_friend)-len(friend_friend_exp))
print(*List)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
F = [[0 for j in range(N)] for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    F[a][b] = 1
    F[b][a] = 1
    for j in range(a, b):
        F[j][j + 1] = 1
        F[j + 1][j] = 1
        # print(i, F)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    F[a][b] = 2
    F[b][a] = 2

# print(F)
ans = []
for i in range(N):
    z = F[i].count(0)
    ans.append(z - 1)

print(*ans)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
CD=[list(map(int,input().split())) for _ in range(k)]

friends=[set() for _ in range(n)]
blocks=[set() for _ in range(n)]
for a,b in AB:
  a,b=a-1,b-1
  friends[a].add(b)
  friends[b].add(a)
for c,d in CD:
  c,d=c-1,d-1
  blocks[c].add(d)
  blocks[d].add(c)

print(friends)
print(blocks)
ans=[0]*n
for i in range(n):
  koho=set()
  for f in friends[i]:
    for ff in friends[f]:
      print(i,f,ff,friends[i],blocks[i])
      if ff not in friends[i] and ff not in blocks[i] and ff!=i:
        koho.add(ff)
  print(koho)
  ans[i]=len(koho)
print(ans)