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: Accepted

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

nmk = input().split()
N = int(nmk[0])
M = int(nmk[1])
K = int(nmk[2])

uf = UnionFind(N+1)
block = [0]*(N+1)

for i in range(M):
    ab = input().split()
    A = int(ab[0])
    B = int(ab[1])
    block[A]+=1
    block[B]+=1
    uf.union(A,B)

ans = [0]*(N+1)

for i in range(1,N+1):
    ans[i] = uf.size(i)-1

for i in range(K):
    cd = input().split()
    C = int(cd[0])
    D = int(cd[1])
    if uf.same(C, D):
        block[C]+=1
        block[D]+=1

for i in range(1,N+1):
    print(ans[i]-block[i])

Submission status: Accepted

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

def resolve():
    N, M, K = list(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 = [0 for _ in range(N)]
    blocks = [0 for _ in range(N)]
    unions = UnionFind(N)
    for a, b in AB:
        unions.union(a-1, b-1)
        friends[a-1] += 1
        friends[b-1] += 1
    for c, d in CD:
        if unions.same(c-1, d-1):
            blocks[c-1] += 1
            blocks[d-1] += 1
    ans = []
    for i in range(N):
        ans.append(unions.size(i)-friends[i]-blocks[i]-1)
    print(*ans)


if '__main__' == __name__:
    resolve()

Submission status: Accepted

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


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

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

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


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

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

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

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

for i in range(n):
    ss=size(i)-1
    rooti=root(i)
    for gi in g[i]:
        if root(gi)==rooti:
            ss-=1
    for xi in x[i]:
        if root(xi)==rooti:
            ss-=1
    print(ss,end=" ")
print(" ")

Submission status: Accepted

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

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

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

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

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


main()

Submission status: Accepted

Solution code:
from collections import deque
#空のリスト 作った後は普通にappend使えばOK
n,m,k=map(int,input().split())
 
tomodati=[[] for i in range(n+1)]
 
group=[0]*(n+1)

group_cnt=[0]*(n+1)
 
block=[0]*(n+1)
 
tansaku=deque()
 
for i in range(m):
    a,b=map(int,input().split())
    tomodati[a].append(b)
    tomodati[b].append(a)
 
num=1
 
for i in range(1,n+1):
    if group[i]==0:
        tansaku.append(i)
        group[i]=num
        group_cnt[num]+=1
    else:
        continue
    while len(tansaku)>0:
        for j in tomodati[tansaku[0]]:
            if group[j]==0:
                group[j]=num
                group_cnt[num]+=1
                tansaku.append(j)
        tansaku.popleft()
    num+=1
 
for i in range(k):
    c,d=map(int,input().split())
    if group[c]==group[d]:
        block[c]+=1
        block[d]+=1
 
ans=[]
 
for i in range(1,n+1):
    ans.append(group_cnt[group[i]]-len(tomodati[i])-block[i]-1)
 
print(*ans)

Submission status: Accepted

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

    G=[[] for i in range(N)]

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

    B=[[] for i in range(N)]
    for i in range(K):
        c,d=map(int,input().split())
        B[c-1].append(d-1)
        B[d-1].append(c-1)
    trace=[-1 for i in range(N)]
    Group=[]

    for i in range(N):
        stack=[]
        if trace[i]==-1:
            trace[i]=0
            stack.append(i)
        Group_tmp=[]
        while len(stack)>0:
            index=stack.pop()
            Group_tmp.append(index)
            for j in G[index]:
                if trace[j]==-1:
                    trace[j]=0
                    stack.append(j)
        if len(Group_tmp)!=0:
            Group.append(Group_tmp)
    res=[0 for i in range(N)]
    GroupMarker=[-1 for i in range(N)]

    for i in range(len(Group)):
        for j in range(len(Group[i])):
            person=Group[i][j]
            GroupMarker[person]=i
            r=len(Group[i])-len(G[person])-1
            res[person]=r

    for i in range(len(B)):
        for j in range(len(B[i])):
            if GroupMarker[i]==GroupMarker[B[i][j]]:
                res[i]-=1
    res=list(map(str,res))
    print(" ".join(res))

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

#import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
group = [0]*(N+1)
g_num = 0
g_cnt = []
for i in range(1,N+1):
  cnt = 0
  if grouping[i] == True:
    continue 
  group[i] = g_num
  grouping[i] = True
  #q = queue.Queue()
  #q.put(i)
  stack = [i]
  #while not q.empty():
  while len(stack)>0:
    #print('v:',visited)
    #p = q.get()
    p = stack.pop()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        #q.put(f)
        stack.append(f)
        group[f]=g_num
        grouping[f] =True
        cnt += 1
  g_num += 1
  g_cnt.append(cnt)
  #print('g:',grouping)
ans = []
for i in range(1,N+1):
  c = g_cnt[group[i]]-len(friend[i])
  for b in block[i]:
    if group[b]==group[i]:
      c -= 1
  ans.append(c)
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y] 

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
      
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

n,m,k=map(int,input().split())
uf=UnionFind(n+1)
cnt=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a,b)
  cnt[a]+=1
  cnt[b]+=1
for _ in range(k):
  c,d=map(int,input().split())
  if uf.is_same(c,d):
    cnt[c]+=1
    cnt[d]+=1
for i in range(1,n+1):
  print(uf.get_size(i)-cnt[i]-1,end=' ')

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.table = [-1 for _ in range(n)]
        self.size = [1]*n

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

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]

    def group_size(self, x):
        return self.size[self._root(x)]

Friends = [list(map(int, input().split())) for _ in range(M)]
Blocks = [list(map(int, input().split())) for _ in range(K)]

Friendship = UnionFind(N)
Cant = [0]*N

for a in Friends:
    Friendship.union(a[0]-1, a[1]-1)

for b in Friends:
    if Friendship.find(b[0]-1, b[1]-1):
        Cant[b[0]-1] += 1; Cant[b[1]-1] += 1

for c in Blocks:
    if Friendship.find(c[0]-1, c[1]-1):
        Cant[c[0]-1] += 1; Cant[c[1]-1] += 1

print(*[Friendship.group_size(i)-Cant[i]-1 for i in range(N)])

Submission status: Accepted

Solution code:
import sys
from collections import Counter as cc
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


class UnionFind():
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.height = [0]*n

    def get_root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.get_root(self.parent[i])
            return self.parent[i]
        
    def unite(self, i, j):
        root_i = self.get_root(i)
        root_j = self.get_root(j)
        if root_i != root_j:
            if self.height[root_i] < self.height[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                if self.height[root_i] == self.height[root_j]:
                    self.height[root_i] += 1
    
    def is_in_group(self, i, j):
        if self.get_root(i) == self.get_root(j):
            return True
        else:
            return False


def main():
    n, m, k= mi()   
    e = [0]*n
    uf = UnionFind(n)     
    for i in range(m):
        a, b = mi()
        a-=1
        b-=1
        e[a]-= 1
        e[b]-= 1
        uf.unite(a,b)
    
    
    for _ in range(k):
        a,b = mi()
        a-=1
        b-=1
        if uf.is_in_group(a,b):
            e[a] -= 1
            e[b] -= 1
        
    for i in range(n):
        uf.get_root(i)
    s = cc(uf.parent)
    for i in range(n):
        x = uf.get_root(i)
        e[i] += s[x]-1
    print(*e)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

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

uf = Uf(N+1)
M = [-1] * (N+1)
for a, b in AB:
    uf.unite(a, b)
    M[a] -= 1
    M[b] -= 1
for c, d in CD:
    if uf.same(c, d):
        M[c] -= 1
        M[d] -= 1
for i in range(1, N+1):
    M[i] += uf.count(i)
print(" ".join(map(str, M[1:])))

Submission status: Accepted

Solution code:
import sys
N, M, K = map(int, input().split())
friends = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)
blocks = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, sys.stdin.readline().split())
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)

done = set()
chains = []
todo = []
for s in range(N):
    if s in done:
        continue
    chain = set()
    todo.append(s)
    while todo:
        i = todo.pop()
        for ni in friends[i]:
            if ni in done:
                continue
            done.add(ni)
            chain.add(ni)
            todo.append(ni)
    chains.append(chain)

ans = [0] * N
for chain in chains:
    for i in chain:
        blocks[i].intersection_update(chain)
        ans[i] = len(chain) - len(blocks[i]) - len(friends[i]) - 1
print(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n: int) -> None:
        self.forest = [-1] * n

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x,y = y,x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

    def findRoot(self, x: int) -> int:
        if self.forest[x] < 0:
            return x
        else:
            self.forest[x] = self.findRoot(self.forest[x])
            return self.forest[x]

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)
    
    def size(self,x: int) -> int:
        return -self.forest[self.findRoot(x)]

n,m,k = map(int,input().split())
l = [[] for _ in range(n)]
u = UnionFind(n)
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    u.union(a,b)
    l[a].append(b)
    l[b].append(a)

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.issame(c,d):
        l[c].append(d)
        l[d].append(c)

for i in range(n):
    q = u.size(i)
    w = len(l[i])
    print(q-w-1, end=" ")

Submission status: Accepted

Solution code:

class UnionFind:
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属するかどうかを返す
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.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()}

    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def resolve():
    N, M, K = map(int, input().split())
    uf = UnionFind(N)
    sub_friend = [1] * N  # +1: 自分自身

    frind = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, input().split())
        frind[a].append(b)
        frind[b].append(a)
        sub_friend[a] += 1
        sub_friend[b] += 1

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

    for i in range(N):
        for to in frind[i]:
            uf.union(i, to)

    ans = [uf.size(i) - sub_friend[i] for i in range(N)]

    for i in range(N):
        for bl in block[i]:
            if uf.is_same(i, bl):
                ans[i] -= 1
    print(*ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)

def resolve():
    N, M,K = map(int, input().split())
    frind = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x:int(x)-1, input().split())
        frind[a].append(b)
        frind[b].append(a)

    block = [[] for _ in range(N)]
    for _ in range(K):
        a, b = map(lambda x: int(x) - 1, input().split())
        block[a].append(b)
        block[b].append(a)


    D = {}
    parent = [-1]*N
    visited = [False]*N
    for root in range(N):
        if visited[root]:
            continue
        D[root] = set([root])
        stack = [root]
        while stack:
            n = stack.pop()
            visited[n] = True
            parent[n] = root
            for to in frind[n]:
                if visited[to]:
                    continue
                D[root].add(to)
                stack.append(to)

    ans = [0]*N
    for i in range(N):
        gr = D[parent[i]]
        tmp = len(gr)-len(frind[i]) - 1
        for bl in block[i]:
            if bl in gr:
                tmp -= 1
        ans[i] = tmp
    print(*ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque, Counter
import sys

N_MAX = 100000 + 5
sys.setrecursionlimit(N_MAX)

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

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

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


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


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

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


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

# print(gr)

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


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

    ans.append(kouho_suu)

print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

class UnionFind():
  def __init__(self, n):
    self.n = n                           # 要素数
    self.parents = [i for i in range(n)] # 要素の親
    self.rank = [0] * n                  # 木の深さ
    self.size = [1] * n                  # iを根とする集合の要素数

  def find(self, x):
    if self.parents[x] == x:
      return x
    else:
      # 経路圧縮
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]
    
  def union(self, x, y):
    root_x = self.find(x)
    root_y = self.find(y)
    
    if root_x != root_y:
      # 深さが小さい方を大きい方に併合する
      if self.rank[root_x] > self.rank[root_y]:
        self.parents[root_y] = root_x
        self.size[root_x] += self.size[root_y]
      else:
        self.parents[root_x] = root_y
        self.size[root_y] += self.size[root_x]
        if self.rank[root_x] == self.rank[root_y]:
          self.rank[root_y] += 1

N, M, K = map(int, input().split())
A = list()
B = list()
C = list()
D = list()
union_find = UnionFind(n=N)
direct_and_block_count = [0] * N
ans = ''
for i in range(M):
  a, b = map(int, input().split())
  A.append(a-1)
  B.append(b-1)
  union_find.union(a-1, b-1)
  direct_and_block_count[a-1] += 1
  direct_and_block_count[b-1] += 1
for i in range(K):
  c, d = map(int, input().split())
  C.append(c-1)
  D.append(d-1)
  if union_find.find(c-1) == union_find.find(d-1):
    # 同じ集合の場合
    direct_and_block_count[c-1] += 1
    direct_and_block_count[d-1] += 1

ans = [0] * N
for i in range(N):
  # 直接の友達、ブロック、自分自身を除く
  ans[i] = union_find.size[union_find.find(i)] - direct_and_block_count[i] - 1
print(*ans)

Submission status: Accepted

Solution code:
import sys
import itertools


class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.par = list(range(n))
        self.rank = [0] * n

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

    def unite(self, x: int, y: int) -> None:
        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: int, y: int) -> bool:
        return self.find(x) == self.find(y)


def resolve(in_):
    N, M, K = map(int, in_.readline().split())
    ab = tuple(tuple(map(int, line.split())) for line in itertools.islice(in_, M))
    cd = tuple(tuple(map(int, line.split())) for line in itertools.islice(in_, K))

    ng = [set() for _ in range(N + 1)]
    friends_tree = UnionFindTree(N + 1)

    for a, b in ab:
        friends_tree.unite(a, b)
    for a, b in ab:
        if friends_tree.same(a, b):
            ng[a].add(b)
            ng[b].add(a)
    for c, d in cd:
        if friends_tree.same(c, d):
            ng[c].add(d)
            ng[d].add(c)
    ok = [0] * (N + 1)
    for i in range(1, N + 1):
        ok[friends_tree.find(i)] += 1    

    ans = [0] * (N + 1)
    for i in range(1, N + 1):
        ans[i] = ok[friends_tree.find(i)] - len(ng[i]) - 1

    return ' '.join(map(str, ans[1:]))


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

par = [-1]*n
num = [0]*n

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

def union(x, y):
    p,q=find(x), find(y)
    if p==q:
        return
    if p>q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p

def size(x):
    return -par[find(x)]

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

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    union(a,b)
    num[a]+=1
    num[b]+=1

for i in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if same(c,d):
        num[c]+=1
        num[d]+=1

for i in range(n):
    print(size(i)-1-num[i], end=" ")

Submission status: Accepted

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())
fr = [0]*n
uf_fr = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf_fr.union(a-1, b-1)
    fr[a-1] += 1
    fr[b-1] += 1

for i in range(k):
    c, d = map(int, input().split())
    if uf_fr.find(c-1) == uf_fr.find(d-1):
        fr[c-1] += 1
        fr[d-1] += 1

ans_list = []
for i in range(n):
    ans_list.append(uf_fr.size(i) - fr[i] - 1)
print(*ans_list)