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
input = sys.stdin.readline

N,M,K=map(int,input().split())
F=[tuple(map(int,input().split())) for i in range(M)]
B=[tuple(map(int,input().split())) for i in range(K)]


# UnionFind

Group = [i for i in range(N+1)] # グループ分け
Nodes = [1]*(N+1) # 各グループのノードの数

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
            
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)




EF=[[] for i in range(N+1)]
EB=[[] for i in range(N+1)]

for x,y in F:
    EF[x].append(y)
    EF[y].append(x)
    Union(x,y)

for x,y in B:
    EB[x].append(y)
    EB[y].append(x)

Group=[find(i) for i in range(N+1)]

GSET=[set() for i in range(N+1)]

for i in range(N+1):
    GSET[find(i)].add(i)

for i in range(1,N+1):
    gr=find(i)
    ANS=len(GSET[gr])-1

    for x in EF[i]:
        if x in GSET[gr]:
            ANS-=1

    for x in EB[i]:
        if x in GSET[gr]:
            ANS-=1

    print(ANS)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False
            
# N, Q = map(int, input().split())
# uni = UnionFind(N)
# for _ in range(Q):
#     P, A, B = map(int, input().split())
#     if P == 1:
#         if uni.root(A) == uni.root(B): #親が同じかどうか
#             print ('Yes')
#         else:
#             print ('No')
#     else:
#         uni.connect(A, B)

import sys
input = sys.stdin.readline

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

direct = [0] * (N + 1)

uni = UnionFind(N + 1)

for _ in range(M):
    A, B = map(int, input().split())
    direct[A] += 1
    direct[B] += 1
    uni.connect(A, B)

ans = [0] * (N + 1)
for i in range(1, N + 1):
    ans[i] = uni.size(i) - direct[i] - 1 #直接の友達と自分自身を引く

for _ in range(K):
    C, D = map(int, input().split())
    if uni.root(C) == uni.root(D):
        ans[C] -= 1
        ans[D] -= 1

for i in range(1, N):
    print (max(0, ans[i]), end = ' ')

print (max(0, ans[N]))

Submission status: Accepted

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            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

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
f = [0] * n
bl = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    f[a - 1] += 1
    f[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    a, b = map(int, input().split())
    if uf.same_check(a - 1, b - 1):
        bl[a - 1] += 1
        bl[b - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.sizeof(i) - f[i] - bl[i] - 1
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b,p,rank,num):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
            num[ap] += num[bp]
        elif rank[ap] < rank[bp]:
            p[ap] = bp
            num[bp] += num[ap]
        else:
            p[bp] = ap
            num[ap] += num[bp]
            rank[ap] += 1

        return False


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

p = [i for i in range(N)]
rank = [1] * N
numlis = [1] * N #自分考慮
linknum = [0] * N

for i in range(M):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    uf_union(A,B,p,rank,numlis)
    linknum[A] += 1
    linknum[B] += 1

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

for i in range(K):

    C,D = map(int,input().split())
    C -= 1
    D -= 1

    dis[C].append(D)
    dis[D].append(C)

al = []

for i in range(N):

    ans = numlis[uf_find(i,p)] - 1 - linknum[i]

    for j in dis[i]:

        if uf_find(i,p) == uf_find(j,p):
            ans -= 1

    al.append(ans)

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

Submission status: Accepted

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

    def find(self, x):
        if self.uf[x]<0: return x
        self.uf[x] = self.find(self.uf[x])
        return self.uf[x]

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

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

F = [0]*N # number of friends
for _ in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)
    F[A-1] += 1
    F[B-1] += 1

G = [0]*N # number of candidates
for i in range(N):
    G[i] = uf.size(i) - F[i] - 1

for _ in range(K):
    C, D = map(int, input().split())
    if uf.find(C-1)!=uf.find(D-1): continue

    G[C-1] -= 1
    G[D-1] -= 1

print(*G)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    conns = [[] for _ in range(N)]
    for i in range(M):
        conns[A[i] - 1].append(B[i] - 1)
        conns[B[i] - 1].append(A[i] - 1)

    par = list(range(N))
    counts = [0] * N
    ret = [0] * N

    def find_root(x):
        if par[x] != x:
            par[x] = find_root(par[x])
        return par[x]

    def is_same_group(a, b):
        a_root = find_root(a)
        b_root = find_root(b)
        return par[a_root] == b_root

    def union(a, b):
        a_root = find_root(a)
        b_root = find_root(b)
        par[a_root] = b_root
        return

    for i in range(M):
        a, b = A[i] - 1, B[i] - 1
        union(a, b)

    for i in range(N):
        root = find_root(i)
        counts[root] += 1

    for i in range(N):
        root = find_root(i)
        ret[i] = counts[root] - len(conns[i]) - 1

    for i in range(K):
        a, b = C[i] - 1, D[i] - 1
        if is_same_group(a, b):
            ret[a] -= 1
            ret[b] -= 1

    print(' '.join([str(r) for r in ret]))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,K = map(int, input().split())
AB = [[int(a) for a in input().split()] for _ in range(M)]
CD = [[int(c) for c in input().split()] for _ in range(K)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
                
    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]


uf = UnionFind(N)
for t in AB:
    uf.unite(t[0], t[1])

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

for i in range(M):
    ans[AB[i][0]-1] -= 1
    ans[AB[i][1]-1] -= 1
for i in range(K):
    if uf.isSameGroup(CD[i][0], CD[i][1]):
        ans[CD[i][0]-1] -= 1
        ans[CD[i][1]-1] -= 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]
        


# coding: utf-8
# Your code here!

import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*a = [int(i) for i in read().split()]
#a = [int(i) for i in readline().split()]
#n = int(input())


n,m,k = [int(i) for i in readline().split()]
ab = [[int(i)-1 for i in readline().split()] for _ in range(m)]
cd = [[int(i)-1 for i in readline().split()] for _ in range(k)]

UF = UnionFind(n)
for a,b in ab:
    UF.merge(a,b)


ans = [UF.getsize(i)-1 for i in range(n)]

for a,b in ab:
    ans[a] -= 1
    ans[b] -= 1

for c,d in cd:
    if UF.issame(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])  # contraction
            return self.par[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]:  # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

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


n, m, k = map(int, input().split())
n_friends = [0] * n
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    uf.unite(a, b)
    n_friends[a] += 1
    n_friends[b] += 1

ans = [uf.size(i) - 1 - n_friends[i] for i in range(n)]

for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
X = [[] for _ in range(N)]
Z = [set() for _ in range(N)] # NG list
for _ in range(M):
    a, b = map(int, input().split())
    X[a-1].append(b-1)
    X[b-1].append(a-1)
    Z[a-1].add(b-1)
    Z[b-1].add(a-1)
for _ in range(K):
    a, b = map(int, input().split())
    Z[a-1].add(b-1)
    Z[b-1].add(a-1)

def col(n, E):
    C = [-1] * n
    CNT = [0] * n
    c = 0
    for i in range(N):
        if C[i] >= 0: continue
        Q = [i]
        C[i] = c
        CNT[c] += 1
        while Q:
            x = Q.pop()
            for y in E[x]:
                if C[y] == -1:
                    C[y] = C[x]
                    CNT[C[y]] += 1
                    Q.append(y)
        c += 1
    return C, CNT

C, CNT = col(N, X)
Y = [0] * N
for i in range(N):
    Y[i] = CNT[C[i]] - 1

for i in range(N):
    for j in Z[i]:
        if C[i] == C[j]:
            Y[i] -= 1
    
print(*Y)

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input

class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if self.size[a] < self.size[b]:
                a, b = b, a

            self.num_sets -= 1
            self.parent[b] = a
            self.size[a] += self.size[b]

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0

n = inp[ii]; ii += 1
m = inp[ii]; ii += 1
k = inp[ii]; ii += 1

count = [-1]*n

dsu = DisjointSetUnion(n)
for _ in range(m):
    a = inp[ii] - 1; ii += 1
    b = inp[ii] - 1; ii += 1
    dsu.union(a,b)
    count[a] -= 1
    count[b] -= 1

for _ in range(k):
    a = inp[ii] - 1; ii += 1
    b = inp[ii] - 1; ii += 1
    if dsu.find(a) == dsu.find(b):
        count[a] -= 1
        count[b] -= 1

for a in range(n):
    count[a] += dsu.size[dsu.find(a)]

print ' '.join(str(x) for x in count)

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(list(self.roots()))

    def all_group_members(self):
        dic = {}
        for x in range(self.N):
            r = self.find(x)
            dic.setdefault(r, [])
            dic[r].append(x)
        return dic

def main():
    N,M,K=map(int, input().split())
    AB=[tuple(map(int, input().split())) for _ in range(M)]
    CD=[tuple(map(int, input().split())) for _ in range(K)]
    UF=UnionFind(N)
    X=[0]*N
    for a,b in AB:
        UF.union(a-1,b-1)
    for i in range(N):
        X[i] += UF.size(i)-1
    for a,b in AB:
        X[a-1]-=1
        X[b-1]-=1
    for c,d in CD:
        if UF.same(c-1,d-1):
            X[c-1]-=1
            X[d-1]-=1
    print(*X)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N)
res = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  res[u] -= 1
  res[v] -= 1
  uf.Unite(u, v)
for _ in range(K):
  u, v = map(int, input().split())
  if uf.isSameGroup(u, v):
    res[u] -= 1
    res[v] -= 1
for i in range(1, N + 1):
  res[i] += uf.Count(i) - 1
print(*res[1: ])

Submission status: Accepted

Solution code:
import sys


class UnionFind:
    def __init__(self, n):
        self.table = [-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 count(self, x):
        return -self.table[self._root(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.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


n, m, k = map(int, sys.stdin.buffer.readline().split())
abcd = list(map(int, sys.stdin.buffer.read().split()))
uft = UnionFind(n)
friends = [0 for _ in range(n)]
blocks = [set() for _ in range(n)]
for a, b in zip(abcd[0:2 * m:2], abcd[1:2 * m:2]):
    a -= 1
    b -= 1
    uft.union(a, b)
    friends[a] += 1
    friends[b] += 1
for c, d in zip(abcd[2 * m::2], abcd[2 * m + 1::2]):
    c -= 1
    d -= 1
    blocks[c].add(d)
    blocks[d].add(c)
ans = []
for i in range(n):
    ans.append(uft.count(i) - 1 - friends[i] - sum(uft.find(i, j) for j in blocks[i]))
print(*ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
par=[-1]*n

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

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True

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

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

F=[-1]*n
for _ in range(m):
  a,b=map(int,input().split())
  unite(a-1,b-1)
  F[a-1]-=1
  F[b-1]-=1
for _ in range(k):
  a,b=map(int,input().split())
  if same(a-1,b-1):
    F[a-1]-=1
    F[b-1]-=1
for i in range(n):
  F[i]+=size(i)
print(*F)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズ
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


import sys
input = sys.stdin.readline

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

P = [1]*(N+1)
uni = UnionFind(N+1)
for a, b in AB:
    P[a] += 1
    P[b] += 1
    uni.Unite(a, b)

ans = []
for n in range(1, N+1):
    ans.append(uni.Count(n)-P[n])

for c, d in CD:
    if uni.isSameGroup(c, d):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx == ry:
        return False
    if uf[rx] > uf[ry]:
        rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

hop1 = [0]*n
dislike = [0]*n
for a,b in ab:
    a,b = a-1, b-1
    unite(a, b)
    hop1[a] += 1
    hop1[b] += 1
for c,d in cd:
    c,d = c-1, d-1
    if root(c) == root(d):
        dislike[c] += 1
        dislike[d] += 1
ans = [-uf[root(i)]-hop1[i]-dislike[i]-1 for i in range(n)]
print(*ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

class UnionFind:
    def __init__(self,n):
        self.ps = [-1]*(n+1)
    def find(self,x):
        if self.ps[x]<0:
            return x
        else:
            self.ps[x]=self.find(self.ps[x])
            return self.ps[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return False
        if self.ps[x]>self.ps[y]:
            x,y = y,x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        x = self.find(x)
        return -self.ps[x]

n,m,k = nm()
ed = [nl() for _ in range(m)]
bl = [nl() for _ in range(k)]
al = [0]*n
uf = UnionFind(n)
for a,b in ed:
    uf.unite(a,b)
    al[a-1] += 1
    al[b-1] += 1
ans = [uf.size(x)-1-al[x-1] for x in range(1,n+1)]
for a,b in bl:
    if uf.same(a,b):
        ans[a-1] -= 1
        ans[b-1] -= 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFindTree:
    """Disjoint-Set Data Structure

    Union-Find Tree

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

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


def main() -> None:
    N, M, K = map(int, input().split())
    uft = UnionFindTree(N)
    ans = [-1] * N
    for i in range(M):
        a, b = map(int, input().split())
        uft.unite(a-1, b-1)
        ans[a-1] -= 1
        ans[b-1] -= 1
    groups = {}
    for i in range(N):
        p = uft.find(i)
        groups[p] = groups.get(p, 0) + 1
    for i in range(N):
        ans[i] += groups[uft.find(i)]
    for i in range(K):
        c, d = map(int, input().split())
        if uft.is_same(c-1, d-1):
            ans[c-1] -= 1
            ans[d-1] -= 1
    print(*ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if x == p[x]:
            return x
        p[x] = root(p[x])
        return p[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if r[x] < r[y]:
            p[x] = y
        else:
            p[y] = x
            if r[x] == r[y]:
                r[x] += 1

    n,m,k = LI()
    p = [i for i in range(n)]
    r = [0]*n
    f = [0]*n
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        if root(a) != root(b):
            unite(a,b)
        f[a] += 1
        f[b] += 1
    for i in range(k):
        a,b = LI()
        a -= 1
        b -= 1
        if root(a) == root(b):
            f[a] += 1
            f[b] += 1
    d = defaultdict(lambda : 0)
    for i in range(n):
        d[root(i)] += 1
    ans = []
    for i in range(n):
        ans.append(d[root(i)]-f[i]-1)
    print(*ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(m)]
cd=[list(map(int,input().split()))for _ in range(k)]
import sys;sys.setrecursionlimit(10**9)
class UnionFind():
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
  def Find_Root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.Find_Root(self.n[x])
      return self.n[x]
  def Unite(self,x,y):
    x=self.Find_Root(x)
    y=self.Find_Root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
  def Root_Same(self,x,y):
    return self.Find_Root(x)==self.Find_Root(y)
  def Count(self,x):
    return -self.n[self.Find_Root(x)]
u=UnionFind(n)
for a,b in ab:u.Unite(a-1,b-1)
ans=[u.Count(i)-1for i in range(n)]
for a,b in ab:
  if u.Root_Same(a-1,b-1):
    ans[a-1]-=1
    ans[b-1]-=1
for c,d in cd:
  if u.Root_Same(c-1,d-1):
    ans[c-1]-=1
    ans[d-1]-=1
print(*ans)