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:
import sys
sys.setrecursionlimit(10**6)
def main():
    class unionfind():
        def __init__(self,n):
            self.par = [i for i in range(n)]
            self.size = [1 for i in range(n)]
            self.rank = [0 for i in range(n)]
 
        def root(self,x):
            if self.par[x] == x:
                return x
            else:
                self.par[x] = self.root(self.par[x])
                return self.par[x]
 
        def same(self,x,y):
            return self.root(x) == self.root(y)
 
        def unite(self,x,y):
            x = self.root(x)
            y = self.root(y)
            if x==y:return
            else:
                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 get_size(self,x):
            x = self.root(x)
            return self.size[x]
 
    
    input = sys.stdin.readline
    n,m,k = map(int,input().split())
    uff = unionfind(n)
    fr = [0 for i in range(n)]
 
 
    for i in range(m):
        a,b = map(int,input().split())
        uff.unite(a-1,b-1)
        fr[a-1]+=1
        fr[b-1]+=1
 
 
    ans = [uff.get_size(i) -fr[i]-1 for i in range(n)]
 
    for i in range(k):
        c,d = map(int,input().split())
        if uff.same(c-1,d-1):
            ans[c-1] -=1
            ans[d-1] -=1
    print(*ans)
if __name__=="__main__":
    main()

Submission status: Accepted

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

class UnionFind():
    def __init__( self, n ):
        self.n = n
        self.parents = [ - 1 ] * n
        
    def find( self, x ):
        if self.parents[ x ] < 0:
            return x
        else:
            self.parents[ x ] = self.find( self.parents[ x ] )
            return self.parents[ x ]

    def union( self, x, y ):
        x = self.find( x )
        y = self.find( y )
        if x == y:
            return
        if self.parents[ x ] > self.parents[ y ]:
            x, y = y, x
        self.parents[ x ] += self.parents[ y ]
        self.parents[ y ] = x
        
    def size( self, x ):
      return -self.parents[ self.find( x ) ]
        
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def same( self, x, y ):
      return self.find( x ) == self.find( y )

uf = UnionFind( N + 1 )
not_use = [ 0 ] * ( N + 1 )
for i in range( M ):
  a, b = map( int, input().split() )
  uf.union( a, b )
  not_use[ a ] += 1
  not_use[ b ] += 1

block = [ [] for _ in range( N + 1 ) ]
for i in range( K ):
  c, d = map( int, input().split() )
  if uf.same( c, d ):
    not_use[ c ] += 1
    not_use[ d ] += 1

ans = str( uf.size( 1 ) - not_use[ 1 ] - 1 )
for i in range( 2, N + 1 ):
  ans += " " + str( uf.size( i ) - not_use[ i ] - 1 )
print( ans )

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

from collections import Counter

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

to = [[] for i in range(N)]
block = [[] for i in range(N)]
sets = []

is_visited = [False] * N
graph_g = [None] * N
graph_cnt = -1

def dfs(s, g):
    global graph_cnt
    if is_visited[s]:
        return 0

    is_visited[s] = True
    if g == None:
        graph_cnt += 1
        graph_g[s] = graph_cnt
    else:
        graph_g[s] = g

    for edge in to[s]:
        if graph_g[edge] == None:
            dfs(edge, graph_cnt)


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

for i in range(N):
    if is_visited[i]:
        continue
    dfs(i, None)

for i in range(K):
    C, D = map(int, input().split())
    if graph_g[C-1] == graph_g[D-1]:
        block[C-1].append(D-1)
        block[D-1].append(C-1)

ct = Counter(graph_g)

ret = []
for i in range(N):
    cand = ct[graph_g[i]]
    fri = len(to[i])
    tmp_block = len(block[i])

    tmp_ret = cand - fri - tmp_block - 1
    ret.append(tmp_ret)

print(*ret)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for k in range(1,N+1):
        tr = belong[k]
        candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

Submission status: Accepted

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

    def find(self, x):
        if self.parents[x] < 0:# - = root
            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]:# - → reverse
            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):# for print
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M, K = map(int, input().split())
    f_uni = UnionFind(N)
    not_cand = [0] * N
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        not_cand[A] += 1
        not_cand[B] += 1
        f_uni.union(A,B)
    
    for _ in range(K):
        C, D = map(int, input().split())
        C -= 1
        D -= 1
        if f_uni.same(C,D):
            not_cand[C] += 1
            not_cand[D] += 1
    ans = [0] * N
    for i in range(N):
        ans[i] = f_uni.size(i) - not_cand[i] - 1
    
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

n,m,k=map(int,input().split())
uf=UnionFind(n)
rmv=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  rmv[a-1].append(b-1)
  rmv[b-1].append(a-1)
  uf.union(a-1,b-1)
for i in range(k):
  c,d=map(int,input().split())
  if uf.find(c-1)==uf.find(d-1):
    rmv[c-1].append(d-1)
    rmv[d-1].append(c-1)
ans=[]
for i in range(n):
  uf.find(i)
  ans.append(str(uf.size[uf.par[i]]-len(rmv[i])-1))
print(" ".join(ans))

Submission status: Accepted

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

n,m,k=map(int,input().split())
uf=UnionFind(n)
rmv=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  rmv[a-1].append(b-1)
  rmv[b-1].append(a-1)
  uf.union(a-1,b-1)
for i in range(k):
  c,d=map(int,input().split())
  if uf.find(c-1)==uf.find(d-1):
    rmv[c-1].append(d-1)
    rmv[d-1].append(c-1)
ans=""
for i in range(n):
  uf.find(i)
  ans+=str(uf.size[uf.par[i]]-len(rmv[i])-1) + " "
print(ans)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
 
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
uf = UnionFind(N)
 
deg = [0]*N
to = [[] for _ in range(N)]
 
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    deg[a] += 1
    deg[b] += 1
 
for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    to[c].append(d)
    to[d].append(c)
 
res = []

for i in range(N):
    r = uf.size(i)-1-deg[i]
    for u in to[i]:
        if uf.same(i, u):
            r -= 1
    res.append(str(r))

print(" ".join(res))

Submission status: Accepted

Solution code:
#Satoooh blog 友達もブロックdiも、まとめて配列direct[i]にappend
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M  # 入力時に 0-index に合わせる
C, D = [0] * K, [0] * K  # 入力時に 0-index に合わせる

direct =[[] for _ in range(N)]  # 同じ集合の友達もしくはブロック関係の人
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

for i in range(K):
    C[i], D[i] = map(int, input().split())
    C[i] -= 1
    D[i] -= 1
    if uf.is_same(C[i], D[i]):
        direct[C[i]].append(D[i])
        direct[D[i]].append(C[i])

ans = [0] * N
for i in range(N):
    ans[i] = uf.group_size(i) - len(direct[i]) - 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1 for i in range(n)]
    def find(self,x):
        if self.parents[x] < 0:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True
    def same(self,x,y):
        return self.find(x) == self.find(y)
    def size(self,x):
        return -self.parents[self.find(x)]

n,m,k = map(int, input().split())
deg = [0 for i in range(n)]
to = [[] for i in range(n)]
uf = UnionFind(n)
for i in range(m):
    a,b = map(int, input().split())
    a -= 1; b -= 1;
    deg[a] += 1
    deg[b] += 1
    uf.unite(a,b)
for i in range(k):
    c,d = map(int, input().split())
    c -= 1; d -= 1;
    to[c].append(d)
    to[d].append(c)
for i in range(n):
    ans = uf.size(i)-1-deg[i]
    for u in to[i]:
        if uf.same(i,u):
            ans -= 1
    if i != n-1:
        print(ans, end=" ")
    else:
        print(ans)

Submission status: Accepted

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

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = [i]
    friend = [i]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)

Submission status: Accepted

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

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = [i]
    friend = [i]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)

Submission status: Accepted

Solution code:
# Union-Find Set

fa = [x for x in range (100002)]
ans = [-1 for i in range (100002)]
siz = [1 for i in range (100002)]
rank = [0 for i in range (100002)]


def find (x) : # find the highest ancestor of x
    fa[x] = x if fa[x] == x else find (fa[x])
    return fa[x]

def union (x, y) :
    # fa[find (x)] = find (y)
    u, v = find (x), find (y)
    if (rank[u] >= rank[v]) :
        fa[v] = u
        if (u != v) :
            siz[u] += siz[v]
        if (rank[u] == rank[v]) :
            rank[u] += 1
    else :
        fa[u] = v
        if (v != u) :
            siz[v] += siz[u]

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

for i in range (M) :
    a, b = list (map (int, input().split()))
    union (a, b)
    ans[a] -= 1
    ans[b] -= 1
    
# TODO : .... build ans[]
for i in range (1, N + 1) :
    ans[i] += siz[find (i)]

# TODO : eliminate blockships
for i in range (K) :
    c, d = list (map (int, input().split()))
    if (find (c) == find (d)) :
        ans[c] -= 1
        ans[d] -= 1

print (' '.join (list (map (str, ans[1:N + 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())

n,m,k = map(int,input().split())
ab = []
cd = []
uf = UnionFind(n)
fr = [0] * n
dis = [0] * n
for i in range(m):
    ab.append(list(map(int,input().split())))
    uf.union(ab[i][0]-1,ab[i][1]-1)
    fr[ab[i][0]-1] += 1
    fr[ab[i][1]-1] += 1
for i in range(k):
    cd.append(list(map(int,input().split())))
    if uf.same(cd[i][0]-1,cd[i][1]-1):
        dis[cd[i][0]-1] += 1
        dis[cd[i][1]-1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i)-fr[i]-dis[i] - 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    #https://note.nkmk.me/python-union-find/ 
    #note.nkmk.me  2019-08-18 
    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())


#初期入力、集合とユニオンファインド
import sys
input = sys.stdin.readline
N,M,K = (int(x) for x in input().split())
AB =set()
CD =set()
friends ={i:set() for i in range(1,N+1)}
uf =UnionFind(N+1) #union_find、1～Nで初期化、sizeは-１必要

for i in range(1,M+1):
    a,b =(int(i) for i in input().split() )
    friends[a].add(b) #友達関係入力
    friends[b].add(a)
    uf.union(a,b)

blocks ={i:set() for i in range(1,N+1)}
for i in range(1,K+1):
    c,d =(int(i) for i in input().split() )
    blocks[c].add(d)#ブロック関係入力
    blocks[d].add(c)
    

friends_candidate={i:set() for i in range(1,N+1) }    
for iam in friends_candidate.keys():
    blocks_same =0 #iamから見て、同じ集合にいるが、blockの人数
    for block in blocks[iam]:
        if uf.same(iam,block):
            blocks_same +=1
    friends_candidate[iam] =uf.size(iam)-1 - len(friends[iam]) - blocks_same  #最初の-1はuf初期化１～Nでしたから
print(*friends_candidate.values())

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(3 * 10 ** 5)

def main():
  n, m, k = map(int, input().split(' '))
  nodes = tuple([([], set()) for i in range(n)])
  for _ in range(m):
    a, b = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[a][0].append(b)
    nodes[b][0].append(a)

  for _ in range(k):
    c, d = sorted(map(lambda x: int(x) - 1, input().split()))
    nodes[c][1].add(d)
    nodes[d][1].add(c)

  total_done_set = set()

  def dfs(node_id, done_set):
    if node_id in done_set: return 0

    total_done_set.add(node_id)
    done_set.add(node_id)

    size = 1
    for child_id in nodes[node_id][0]:
      size += dfs(child_id, done_set)

    return size


  ans_list = [-1] * n

  def dfs2(node_id, connected_ids, total_len):
    children, block_id_set = nodes[node_id]
    ans_list[node_id] = total_len - len(list(filter(
      lambda block_id: block_id in connected_ids, block_id_set
    ))) - 1

    except_num = 0
    for child_id in children:
      if child_id not in block_id_set:
        except_num += 1

      if ans_list[child_id] == -1:
        dfs2(child_id, connected_ids, total_len)

    ans_list[node_id] -= except_num


  for i in range(n):
    if i not in total_done_set:
      done_set = set()
      dfs(i, done_set)
      dfs2(i, done_set, len(done_set))

  print(*ans_list, sep=" ")


main()

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
import sys
rks = [None] *n
sys.setrecursionlimit(10**9)
fgraph = [list() for i in range(n)]
bgraph = [list() for i in range(n)]
cgraph = [list() for i in range(n)]
g = [[]for i in range(n)]
for i in range(m):
        a,b = map(int, input().split())
        fgraph[a-1].append(b)
        fgraph[b-1].append(a)
def dfs(graph,s,r):
    if rks[s] is None:
        rks[s] = r
    for i in range(len(graph[s])):
        if rks[graph[s][i]-1] is not None:
            continue
        g[r].append(0)
        dfs(graph, graph[s][i]-1,r)
c = -1
for i in range(n):
    if rks[i] is None:
        c += 1
        dfs(fgraph, i, c)
for i in range(k):
        c,d = map(int, input().split())
        if rks[c-1] == rks[d-1]:
            bgraph[d-1].append(c)
            bgraph[c-1].append(d)
for i in range(n):
        print(len(g[rks[i]]) - len(fgraph[i]) - len(bgraph[i]) )

Submission status: Accepted

Solution code:

def tramp(gen):
    stack = [gen]
    val = None
    while stack:
        try:
            stack.append(stack[-1].send(val))
            val = None
        except StopIteration as e:
            stack.pop()
            val = e.args
    return val
    
N, M, K = map(int, input().split())
adj = [[] for _ in range(N)]
blks = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
for _ in range(K):
    a, b = map(int, input().split())
    blks[a - 1].add(b - 1)
    blks[b - 1].add(a - 1)
vis = [False] * N
def go(curr):
    if vis[curr]:
        return
    vis[curr] = True
    comp.add(curr)
    for n in adj[curr]:
        yield go(n)
ans = [0] * N
for i in range(N):
    comp = set()
    if vis[i]:
        continue
    tramp(go(i))
    for i in comp:
        x = len(comp) - 1 - len(adj[i])
        for k in blks[i]:
            if k in comp:
                x -= 1
        ans[i] = x
print(*ans)

Submission status: Accepted

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

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

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


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


UF = UnionFind(N)
for iam in range(N):
    for friend in F[iam]:
        UF.unite(iam, friend)

ans = [UF.size[UF.find(iam)] - 1 for iam in range(N)]
for iam in range(N):
    ans[iam] -= len(F[iam])

for iam in range(N):
    for block in B[iam]:
        if UF.find(iam) == UF.find(block):
            ans[iam] -= 1

print(*ans, sep=' ')

Submission status: Accepted

Solution code:
# union fine tree

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

# init
parent = [i for i in range(n)]
rank = [1] * n
size = [1] * n

def find(x):
	if parent[x] == x:
		return x
	else:
		parent[x] = find(parent[x])
		return parent[x]

def unite(x, y):
	x, y = find(x), find(y)
	if x == y:
		return 
	if rank[x] < rank[y]:
		parent[x] = y
		size[y] += size[x]
	else:
		parent[y] = x
		size[x] += size[y]
		if rank[x] == rank[y]:
			rank[x] += 1

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

def groupSize(x):
	return size[find(x)]

A, B = [0] * m, [0] * m
C, D = [0] * k, [0] * k

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

for i in range(m):
	a, b = map(int, input().split())
	A[i] = a - 1
	B[i] = b - 1
	net[A[i]].append(B[i])
	net[B[i]].append(A[i])
	unite(A[i], B[i])

for i in range(k):
	c, d = map(int, input().split())
	C[i] = c - 1
	D[i] = d - 1
	if same(C[i], D[i]):
		net[C[i]].append(D[i])
		net[D[i]].append(C[i])

res = [0] * n
for i in range(n):
	res[i] = groupSize(i) - len(net[i]) - 1
print(*res)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


class UnionFind:
    def __init__(self, n_nodes):
        self.parent = [i for i in range(n_nodes)]
        self.rank = [0] * n_nodes
        self.size = [1] * n_nodes

    def find(self, x):
        if x == self.parent[x]:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[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.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


N, M, K = map(int, input().split())
tree = UnionFind(N)
exclusion = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree.unite(a, b)
    exclusion[a].append(b)
    exclusion[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if not tree.check(c, d):
        continue
    exclusion[c].append(d)
    exclusion[d].append(c)

for i in range(N):
    # 同一グループで自分以外の人数
    n = tree.get_size(i) - 1
    ans = n - len(exclusion[i])
    print(ans, end=" ")