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:
# UnionFind木
class UnionFind:
    def __init__(self, n):
        # その節の根、その節を含む木の高さ、その節が根の時の木のノード数
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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 union(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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            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 getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    # 広義の友達 - 直接の友達 - ブロック
    # UnionFind木
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [""] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = str(uftree.getSize(i) - 1 - count[i]) # 真ん中の-1は自分自身
    print(*ans)

main()

Submission status: Wrong Answer

Solution code:
# UnionFind木
class UnionFind:
    def __init__(self, n):
        # その節の根、その節を含む木の高さ、その節が根の時の木のノード数
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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 union(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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            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 getSize(self, x):
        return self.size[self.find(x)]

def main():
    N,M,K = map(int, input().split())
    # 広義の友達 - 直接の友達 - ブロック
    # UnionFind木
    uftree = UnionFind(N)
    count = [0] * N
    for i in range(M):
        A,B = map(lambda x:x-1, map(int, input().split()))
        uftree.union(A,B)
        count[A] += 1
        count[B] += 1
    for i in range(K):
        C,D = map(lambda x:x-1, map(int, input().split()))
        if uftree.same_check(C,D):
            count[C] += 1
            count[D] += 1
    ans = [""] * N
    for i in range(N):
        print(uftree.getSize(i))
        print(count[i])
        ans[i] = str(uftree.getSize(i) - 1 - count[i]) # 真ん中の-1は自分自身
    print(" ".join(ans))

main()

Submission status: Wrong Answer

Solution code:
N,M,K=map(int, input().split())
s=[[]for i in range(N+1)]
for i in range (M+K):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)

from collections import deque
ans=[0]*N
for i in range(1,N+1):
    sumi=[0]*(N+1)
    q=deque(s[i])
    while q:
        a=q.popleft()
        if sumi[a]==0:
            sumi[a]=1
            for a0 in s[a]:
                q.append(a0)
    ans[i-1]=sum(sumi)-len(s[i])-1
print(' '.join(''.join(map(str, ans))))

Submission status: Wrong Answer

Solution code:
N,M,K=map(int, input().split())
s=[[]for i in range(N+1)]
for i in range (M+K):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)

from collections import deque
ans=[0]*N
for i in range(1,N+1):
    sumi=[0]*(N+1)
    q=deque(s[i])
    while q:
        a=q.popleft()
        if sumi[a]==0:
            sumi[a]=1
            for a0 in s[a]:
                q.append(a0)
    ans[i-1]=sum(sumi)-len(s[i])-1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,k = map(int, input().split(" "))
dp =[[0]*n]*n
friend=[]
for i in range(n):
  dp[i][i] = 1
for i in range(m):
  a,b = map(int, input().split(" "))
  friend.append([a,b])
  dp[a-1][b-1] = 2
  dp[b-1][a-1] = 2
for i in range(k):
  c,d = map(int, input().split(" "))
  dp[c-1][d-1] = 3
  dp[d-1][c-1] = 3
for i in friend:
  a = i[0]
  b = i[1]
  for x ,y  in enumerate(dp[a-1]):
    if y==2:
      dp[b-1]

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque

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

f_set = {tuple(map(int,input().split())) for _ in range(m)}

b_set = {tuple(map(int,input().split())) for _ in range(k)}


friends_counts = {key:[] for key in range(1,n+1)}
blocks_counts = {key:[] for key in range(1,n+1)}

for f in f_set:
    friends_counts[f[0]].append(f[1])
    friends_counts[f[1]].append(f[0])

for b in b_set:
    blocks_counts[b[0]].append(b[1])
    blocks_counts[b[1]].append(b[0])



friends_groups_dict = defaultdict(list)

#dfs
que = deque()
groups_count = 0
checked_dict = {key:0 for key in range(1,n+1)}
#que.appendleft(1)

for i in range(1,n+1):
    if checked_dict[i] == 1:
        continue
    que.appendleft(i)
    checked_dict[i] = 1

    while que:
        x = que.popleft()
        friends_groups_dict[groups_count].append(x)
        for i in range(len(friends_counts[x])):
            if checked_dict[friends_counts[x][i]] == 0:
                que.appendleft(friends_counts[x][i])
            checked_dict[friends_counts[x][i]] = 1

    groups_count += 1


result_list=[0]*n

for i in range(len(friends_groups_dict)):
    mini_list = friends_groups_dict[i]
    for j in range(len(mini_list)):
        result_list[mini_list[j]-1] = len(mini_list) - 1 - len(friends_counts[mini_list[j]])
        
        block_counter_in_minilist = 0

        #for k in range(len(blocks_counts[mini_list[j]])):
        #    if blocks_counts[mini_list[j]][k] in mini_list:
        #        block_counter_in_minilist += 1
        #
        #result_list[mini_list[j]-1] -= block_counter_in_minilist
 
print(" ".join(map(str,result_list)))



#cの配列の解釈が違ったらしい。。。
#f_set = {tuple(map(int,input().split())) for _ in range(m)}
#
#b_set = {tuple(map(int,input().split())) for _ in range(k)}
#
#c_list = [0] * (n-1)
#
#result_dict = {key:0 for key in range(1,n+1)}
#
#for f in f_set:
#    if abs(f[0]-f[1]) == 1:
#        c_list[min(f[0],f[1]) - 1] = 1
#    #ここでelseで飛び石での友達のsetを作ってもよいが、そもそもsetなのでinでの探索にそんなに時間かからないし、いったんこのままやってみる。
#
#for start in range(0,n-2):
#    if c_list[start] == 0:
#        #c[start]が1になるまで飛ばす
#        continue
#
#    for end in range(start+1,n-1):
#        if c_list[end] == 0:
#            #友人同士ではないペアまできたらstartをインクリメント
#            break
#        
#        #もし「友人候補」の候補者が、「友人関係でない」かつ「ブロック関係でない」ことをチェックしている。
#        if not (start+1,end+2) in f_set and not (end+2,start+1) in f_set and not (start+1,end+2) in b_set and not (end+2,start+1) in b_set:
#            result_dict[start+1] += 1
#            result_dict[end+2] += 1
#
#for i in range(1,n+1):
#    print(result_dict[i])
#
#print(c_list)

Submission status: Wrong Answer

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            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]

N, M, K = map(int, input().split())
friends_uf = UnionFind(N)
counts = [0] * N
for _ in range(M):
    i, j = map(lambda n: int(n) - 1, input().split())
    counts[i] += 1
    counts[j] += 1
    friends_uf.union(i, j)
blocks_uf = UnionFind(N)
for _ in range(K):
    blocks_uf.union(*map(lambda n: int(n) - 1, input().split()))
for i in range(N):
    ans = friends_uf.size(i) - counts[i]
    for j in friends_uf.members(i):
        if blocks_uf.same(i, j):
            ans -= 1
    print(ans, end=" ")

Submission status: Wrong Answer

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            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]

N, M, K = map(int, input().split())
friends_uf = UnionFind(N)
counts = [0] * N
for _ in range(M):
    i, j = map(lambda n: int(n) - 1, input().split())
    counts[i] += 1
    counts[j] += 1
    friends_uf.union(i, j)
blocks_uf = UnionFind(N)
for _ in range(K):
    blocks_uf.union(*map(lambda n: int(n) - 1, input().split()))
print(*(friends_uf.size(i) - counts[i] - len(set(friends_uf.members(i)) & set(blocks_uf.members(i))) for i in range(N)))

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
friends=[]
block=[[] for _ in range(N+1)]
f=[[] for _ in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)

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

belong=[-1 for _ in range(N+1)]
numofgroup=0
for i in range(1,N+1):
    leader=False
    if belong[i]==-1:
        belong[i]=numofgroup
        leader=True
    for friend in f[i]:
        belong[friend]=belong[i]
    numofgroup+=leader

groupmember=[[] for _ in range(numofgroup)]
for i in range(1,N+1):
    groupmember[belong[i]].append(i)

for i in range(1,N+1):
    g=belong[i]
    res=len(set(groupmember[g])-set(block[i])-set(f[i]))-1
    print(res,end=" ")

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
friends=[]
block=[[] for _ in range(N+1)]
f=[[] for _ in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)

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

belong=[-1 for _ in range(N+1)]
numofgroup=0
for i in range(1,N+1):
    leader=False
    if belong[i]==-1:
        belong[i]=numofgroup
        leader=True
    for friend in f[i]:
        belong[friend]=belong[i]
    numofgroup+=leader

groupmember=[[] for _ in range(numofgroup)]
for i in range(1,N+1):
    groupmember[belong[i]].append(i)

for i in range(1,N+1):
    g=belong[i]
    res=len(set(groupmember[g])-set(block[i])-set(f[i]))-1
    print(res,end="")

Submission status: Wrong Answer

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            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())


n,m,k=map(int,input().split())
uf=UnionFind(n)
block={}
for i in range(n):
    block[i]=[i]
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1].append(b-1)
    block[b-1].append(a-1)
    
for i in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
print(block)
for i in range(n):
    res=uf.size(i)
    print(res)
    for value in block[i]:
        if uf.same(value,i):
            res-=1
    ans.append(res)
print(*ans)

Submission status: Wrong Answer

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[i]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1
       #         print("a")

      #  print(Vstd)
    #    for x in Vstd:
     #       num[x]=len(Vstd)
      #      for y in Vstd:
       #         if y in ng[x] or y in root[x]:
        #            num[x]-=1
    print(*num)
    #print(" ".join(map(str,num)))
   

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import queue
def main():
    n,m,k=map(int,input().split())
    root={}
    ng={}
    for i in range(n):
        root[i]=[]
        ng[i]=[i]
    for i in range(m):
        a,b=map(int,input().split())
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    for i in range(k):
        a,b=map(int,input().split())
        ng[a-1].append(b-1)
        ng[b-1].append(a-1)
    
    Vstd=[]
    checkVst=[0]*n
    num=[0]*n
    ToVst=queue.Queue()
    for i in range(n):
        Vstd=[]
        if checkVst[i]==1:
            continue
        now=i
        Vstd.append(now)
        checkVst[now]=1
        for kouho in root[now]:
            if checkVst[kouho]!=1:
                ToVst.put(kouho)
                checkVst[kouho]=1
        while ToVst.empty()==False:
            now=ToVst.get()
            Vstd.append(now)
            checkVst[now]=1
            for kouho in root[now]:
                if checkVst[kouho]==1:
                    continue
                ToVst.put(kouho)
                checkVst[kouho]=1
       #         print("a")

      #  print(Vstd)
        for x in Vstd:
            num[x]=len(Vstd)
            for y in Vstd:
                if y in ng[x] or y in root[x]:
                    num[x]-=1
    print(" ".join(map(str,num)))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #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 all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

def main():
    n,m,k=map(int,input().split())
    AB=[tuple(map(int,input().split())) for i in range(m)]
    CD=[tuple(map(int,input().split())) for i in range(k)]
    un=UnionFind(n)
    friend=[[] for _ in range(n)]
    for a,b in AB:
        un.unite(a-1,b-1)
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
    block=[[] for _ in range(n)]
    for c,d in CD:
        block[c-1].append(d-1)
        block[d-1].append(c-1)
    for i in range(n):
        print(un.size(i)-1-len(block[i])-len(friend[i]))
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
friends = [0 for _ in range(N)]
blocks = [0 for _ in range(N)]

class Union():
    def __init__(self, N):
        self.Parent = []
        for i in range(N):
            self.Parent.append(-1)

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

    def size(self, A):
        return int(-1 * self.Parent[self.root(A)])

    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return False

        if(self.size(A) < self.size(B)):
            A, B = B, A
        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True

uni = Union(N)
ans = []
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A] += 1
    friends[B] += 1
    uni.connect(A,B)

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if (uni.root(uni.Parent[C]) == uni.root(uni.Parent[D])):
        blocks[C] += 1
        blocks[D] += 1

for i in range(N):
    ansi = max(0, uni.size(i) - friends[i] - blocks[i] - 1)
    ans.append(str(ansi))

print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
friends=[]
block=[[] for _ in range(N+1)]
f=[[] for _ in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)
    friends.append(list((a,b)))
    friends[-1].sort()
friends.sort()

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

belong=[-1 for _ in range(N+1)]
numofgroup=0
index=0
for i in range(1,N+1):
    leader=False
    if belong[i]==-1:
        belong[i]=numofgroup
        leader=True
    while(index<M and friends[index][0]==i):
        belong[friends[index][1]]=belong[i]
        index+=1
    numofgroup+=leader

groupmember=[[] for _ in range(numofgroup)]
for i in range(1,N+1):
    groupmember[belong[i]].append(i)

for i in range(1,N+1):
    g=belong[i]
    res=len(set(groupmember[g])-set(block[i])-set(f[i]))-1
    print(res,end=" ")

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
friends = [0 for _ in range(N)]
blocks = [0 for _ in range(N)]

class Union():
    def __init__(self, N):
        self.Parent = []
        for i in range(N):
            self.Parent.append(-1)

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

    def size(self, A):
        return int(-1 * self.Parent[self.root(A)])

    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return False

        if(self.size(A) < self.size(B)):
            A, B = B, A
        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True

uni = Union(N)
ans = []
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A] += 1
    friends[B] += 1
    uni.connect(A,B)

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if (uni.root(uni.Parent[C]) == uni.root(uni.Parent[D])):
        blocks[C] += 1
        blocks[D] += 1

for i in range(N):
    ansi = uni.size(i) - friends[i] - blocks[i] - 1
    ans.append(str(ansi))

print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def size(self,x):
        #xが属するグループの要素数
        return -self.parents[self.find(x)]
    def same(self,x,y):
        #xとyが同じグループ？
        return self.find(x)==self.find(y)
    def members(self,x):
        #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 all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
    def __str__(self):
        #各ルート要素のグループに含まれる要素のリストをprint()
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels)==len(set(labels))
        self.n=len(labels)
        self.parents=[-1]*self.n
        self.d={x: i for i,x in enumerate(labels)}
        self.d_inv={i: x for i,x in enumerate(labels)}
    def find_label(self,x):
        return self.d_inv[super().find(self.d[x])]
    def unite(self,x,y):
        super().unite(self.d[x],self.d[y])
    def size(self,x):
        return super().size(self.d[x])
    def same(self,x,y):
        return super().same(self.d[x],self.d[y])
    def members(self,x):
        root=self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [self.d_inv[i] for i,x in enumerate(self.parents) if x<0]

def main():
    n,m,k=map(int,input().split())
    AB=[tuple(map(int,input().split())) for i in range(m)]
    CD=[tuple(map(int,input().split())) for i in range(k)]
    un=UnionFindLabel(range(1,n+1))
    friend=[[] for _ in range(n)]
    for a,b in AB:
        un.unite(a,b)
        friend[a-1].append(b)
        friend[b-1].append(a)
    block=[[] for _ in range(n)]
    for c,d in CD:
        block[c-1].append(d)
        block[d-1].append(c)
    print(block)
    for i in range(1,n+1):
        print(len([x for x in un.members(i) if x!=i and (not x in block[i-1]) and  (not x in friend[i-1])]))
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import queue
n, m, k = map(int,input().split())
frnd = [[] for i in range(n+1)]
blck = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    frnd[a].append(b)
    frnd[b].append(a)

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

#グラフをグループ化するやつ
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n+1)]
    q = queue.Queue()
    for i in range(1,n+1):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

fg = grouping(n,frnd)

gn = [0 for i in range(n+1)]
for i,g in enumerate(fg):
    for p in g:
        gn[p] = i
'''
ans = [0 for i in range(n)]
for i in range(1,n+1):
    num = 0
    for pi in fg[gn[i]]:
        if pi == i or pi in frnd[i] or pi in blck[i]:
            continue
        else:
            num += 1
    ans[i-1] = num
'''
print(gn)

Submission status: Wrong Answer

Solution code:
import queue
n, m, k = map(int,input().split())
frnd = [[] for i in range(n+1)]
blck = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    frnd[a].append(b)
    frnd[b].append(a)

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

#グラフをグループ化するやつ
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n+1)]
    q = queue.Queue()
    for i in range(1,n+1):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

fg = grouping(n,frnd)

print(fg)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def dfs(f, v, seen):
    seen[v] = True

    for nv in f[v]:
        if seen[nv]:
            continue
        dfs(f, nv, seen)


def main():
    n, m, k = map(int, stdin.readline().split())

    f = [[] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        f[a - 1].append(b - 1)
        f[b - 1].append(a - 1)

    b = [[] for _ in range(n)]

    for _ in range(k):
        c, d = map(int, stdin.readline().split())
        b[c - 1].append(d - 1)
        b[d - 1].append(c - 1)

    ans = [0] * n

    u = [-1] * n
    uid = 0
    for i in range(n):
        if u[i] != -1:
            seen = [False] * n
            dfs(f, i, seen)
            for j in range(n):
                if seen[j]:
                    u[j] = uid
        uid += 1

    for i in range(n):
        uid = u[i]
        arr = [i for i in range(n) if u[i] == uid]
        tmp = len(set(arr) - set(f[i]) - set(b[i]))
        tmp -= 1
        ans[i] = tmp

    print(*ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

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

n,m,k=map(int,input().split())
fr=[0 for _ in range(n)]
frl=[[] for i in range(n)]
frlist=[]
for i in range(m):
    a,b=map(int,input().split())
    frl[a-1].append(b)
    frl[b-1].append(a)
    frlist.append([a,b])

treelist=[]
hitobito=set()

def saiki(c,tmpi):
    global hitobito
    global tmpset
    global trbl
    
    if frl[c-1] == []:
        hitobito.add(c)
        tmpset.add(c)
        trbl[c-1]=tmpi
    
    for tsugi in frl[c-1]:
        if not tsugi in hitobito:
            hitobito.add(tsugi)
            tmpset.add(tsugi)
            trbl[tsugi-1]=tmpi
            saiki(tsugi,tmpi)

index=0
trbl=[None for _ in range(n)]
for i in range(n):
    tmpset=set()
    saiki(i+1,index)
    if not tmpset == set():
        treelist.append(tmpset)
        index+=1

bl=[0 for _ in range(n)]
bll=[[] for i in range(n)]
bllist=[]
for i in range(k):
    a,b=map(int,input().split())
    bll[a-1].append(b)
    bll[b-1].append(a)
    bllist.append([a,b])

for fre in frlist:
    if trbl[fre[0]-1] == trbl[fre[1]-1]:
        fr[fre[0]-1]=fr[fre[0]-1]+1
        fr[fre[1]-1]=fr[fre[1]-1]+1

for blo in bllist:
    if trbl[blo[0]-1] == trbl[blo[1]-1]:
        bl[blo[0]-1]=bl[blo[0]-1]+1
        bl[blo[1]-1]=bl[blo[1]-1]+1

output=[]
print(trbl)
for i in range(n):
    tmpsum=fr[i]+bl[i]
    output.extend([str(len(treelist[trbl[i]])-tmpsum-1)," "])

print("".join(output))