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

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

        if x == y:
            return

        if (-self.parents[x]) < (-self.parents[y]):
            self.parents[y] += self.parents[x]
            self.parents[x] = y
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x

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

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

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

uf = UnionFind(N)
friends = [0] * N
blocks = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.unite(a, b)
    friends[a] += 1
    friends[b] += 1

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

for i in range(N):
    print(uf.size(i) - friends[i] - blocks[i] - 1, end=" ")
print("")

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        # parent[x] < 0 means x is root and abs(parent[x]) == size[x]
        self.parent, self.depth = [-1] * n, [0] * n

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

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

    def unite(self, x, y):
        if self.isSame(x, y):
            return
        x, y = self.find(x), self.find(y)

        if self.depth[x] > self.depth[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.depth[x] == self.depth[y]:
                self.depth[y] += 1

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


N, M, K = map(int, input().split())
Friend, Block = {i: [] for i in range(N)}, {i: [] for i in range(N)}
union = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    union.unite(A - 1, B - 1)
    Friend[A - 1].append(B - 1)
    Friend[B - 1].append(A - 1)
for _ in range(K):
    C, D = map(int, input().split())
    Block[C - 1].append(D - 1)
    Block[D - 1].append(C - 1)

ans = []
for i in range(N):
    nBlock = 0
    for b in Block[i]:
        if union.isSame(i, b):
            nBlock += 1
    ans.append(str(union.size(i) - 1 - len(Friend[i]) - nBlock))
print(' '.join(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict


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

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

    def union(self, x, y):
        """要素xが属するグループと要素yが属するグループをくっつける
        """
        x = self.find(x)
        y = self.find(y)
        # すでにくっつてるのでそのまま返す
        if x == y:
            return
        # 大きい方(x)に小さい方(y)をくっつけたいので、
        # 大小が逆なら入れ替える
        if self.size(x) < self.size(y):
            x, y = y, x
        # xのサイズを更新する
        self.parents[x] += self.parents[y]
        # yの親をxに変更する
        self.parents[y] = x

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


friends = defaultdict(list)
N, M, K = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    friends[a].append(b)
    friends[b].append(a)

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

ans = []
for i in range(N):
    tmp = uf.size(i) - len(friends[i]) - 1
    for g in groups[i]:
        if uf.find(i) == uf.find(g):
            tmp -= 1
    ans.append(str(tmp))

print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys


class UnionFind():
    def __init__(self, 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 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 size(self, x):
        return -self.parents[self.find(x)]

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


readline = sys.stdin.readline
n, m, k = map(int, readline().split())
ab = tuple(tuple(map(int, readline().split())) for i in range(m))
cd = (map(int, readline().split()) for i in range(k))

friend_group = UnionFind(n)
for a, b in ab:
    friend_group.union(a-1, b-1)

ans = [friend_group.size(i) - 1 for i in range(n)]
for a, b in ab:
    ans[a-1] -= 1
    ans[b-1] -= 1
for c, d in cd:
    if friend_group.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]
        self.sizes[y] = self.sizes[x]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n = n
        
        # parents が負の時は要素数
        # parents が正の時は親の番号
        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)

        # 根が同じ場合はreturn
        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 same(self,x,y):
        return self.find(x) == self.find(y)


N,M,K = (int(x) for x in input().split())

uf = UnionFind(N)
n_friend = [0]*N

for i in range(M):
    A,B = (int(x) for x in input().split())

    A -= 1
    B -= 1

    n_friend[A] += 1
    n_friend[B] += 1
    uf.union(A,B)

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

for i in range(K):
    C,D = (int(x) for x in input().split())

    C -= 1
    D -= 1

    if uf.same(C,D):
        ans[C] -= 1
        ans[D] -= 1

print(*ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

class UnionFind:
    d = {}

    def __init__(self,n):
        self.d = {i:-1 for i in range(n)}

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.d[x] > self.d[y]):
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

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


n,m,k = mi()

uf = UnionFind(n)

block = {}
friend = {}
for i in range(n):
    block[i] = []
    friend[i] = []

for i in range(m):
    ab = li()
    uf.union(ab[1]-1, ab[0]-1)
    friend[ab[0]-1].append(ab[1]-1)
    friend[ab[1]-1].append(ab[0]-1)

for i in range(k):
    cd = li()
    block[cd[0]-1].append(cd[1]-1)
    block[cd[1]-1].append(cd[0]-1)


for i in range(n):
    ans = uf.size(i) - 1 - len(friend[i])
    for j in block[i]:
        if(uf.same(i, j)):
            ans -=1
    
    print(ans)

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:
import sys

sys.setrecursionlimit(10 ** 9)

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # これかああああ！！！！
        # 逆にするといいらしいけどなぜ？
        # if y < x:
        #     x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]
        self.sizes[y] = self.sizes[x]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
 def __init__(self,n):
   self.n=n
   self.root=[-1]*(n+1)
   self.rank=[0]*(n+1)
 def FindRoot(self,x):
   if self.root[x]<0:
     return x
   else:
     self.root[x]=self.FindRoot(self.root[x])
     return self.root[x]
 def Unite(self,x,y):
   x=self.FindRoot(x)
   y=self.FindRoot(y)
   if x==y:
     return
   else:
     if self.rank[x]>self.rank[y]:
       self.root[x]+=self.root[y]
       self.root[y]=x
     elif self.rank[x]<=self.rank[y]:
       self.root[y]+=self.root[x]
       self.root[x]=y
       if self.rank[x]==self.rank[y]:
         self.rank[y]+=1
 def isSameGroup(self,x,y):
   return self.FindRoot(x)==self.FindRoot(y)
 def Count(self,x):
   return -self.root[self.FindRoot(x)]
 
n,m,k=map(int,input().split())
t=UnionFind(n)
cnt=[0]*(n+1) #各iについて、iと同一の連結成分に属する友達関係の人、ブロック関係の人の数を数える
for _ in range(m):
 a,b=map(int,input().split())
 cnt[a]+=1 #各iについて、iと同一の連結成分に属する友達関係の人の数を数える
 cnt[b]+=1
 t.Unite(a,b)
for _ in range(k):
 a,b=map(int,input().split())
 if t.isSameGroup(a,b)==True:
   cnt[a]+=1 #各iについて、iと同一の連結成分に属するブロック関係の人の数を数える
   cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
 ans[i]=(t.Count(i)-1)-cnt[i] #答えは(各iが属する連結成分のサイズ)-1-((iと同一の連結成分に含まれているiと友達関係にある人の数)+(iと同一の連結成分に含まれているiとブロック関係にある人の数)となる
print(*ans[1:])

Submission status: Accepted

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


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    uf = UnionFind(N+1)
    for a, b in zip(A, B):
        uf.union(a, b)
    fr = [uf.size(i)-1 for i in range(N+1)]
    for a, b in zip(A, B):
        fr[a] -= 1
        fr[b] -= 1
    for c, d in zip(C, D):
        if not uf.same(c, d):
            continue
        fr[c] -= 1
        fr[d] -= 1
    return fr[1:]


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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))
    print(*solve(N, M, K, A, B, C, D), sep=' ')

# https://note.nkmk.me/python-union-find/
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())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

N,M,K = [int(x) for x in stdin.readline().rstrip().split()]
F = []

par = [i for i in range(N+1)]
rank = [0] * (N+1)
size = [1] * (N+1)

def find(x):
    if par[x] == x:
        return par[x]
    else:
        par[x] = find(par[x])
        return par[x]
 
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
        size[y] += size[x]
        size[x] = 0
        
    else:
        par[y] = x
        size[x] += size[y]
        size[y] = 0
        if rank[x] == rank[y]:
            rank[x] += 1
 
def check_same(x,y):
    return find(x) == find(y)
 
def check_size(x):
    return size[find(x)]

friends = defaultdict(set)
for _ in range(M):
    A,B = [int(x) for x in stdin.readline().rstrip().split()]
    union(A,B)
    
    friends[A].add(B)
    friends[B].add(A)


block = defaultdict(set)
for _ in range(K):
    C,D = [int(x) for x in stdin.readline().rstrip().split()]
    block[C].add(D)
    block[D].add(C)

for i in range(1,N+1):
    ans = check_size(i)
    ans = ans - 1 - len(friends[i])
    for j in block[i]:
        if check_same(i,j):
          ans -= 1
    print(ans,end=" ")

Submission status: Accepted

Solution code:

# # # # unionfind.py # # # #

# usage: uf = Unionfind(n) ; x = uf.root(y); uf.conn(a,b)

class Unionfind:

  def __init__(s,n):
    s.sz = [1] * n
    s.ances = [i for i in range(n)]
  
  def root(s,x):
    a = []
    y = x
    while s.ances[y] != y:
      a.append(y)
      y = s.ances[y]
    for z in a:
      s.ances[z] = y
    return y
  
  def conn(s,x,y):
    i = s.root(x)
    j = s.root(y)
    if i==j:
      return
    #k  = [i,j].min
    k  = j if (s.sz[i]<s.sz[j]) else i
    if k==j:
      s.ances[i] = j
    else:
      s.ances[j] = i
    s.sz[k] = s.sz[i] + s.sz[j]
  
# # # # end unionfind.py # # # #

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


n,m,k = inm()
uf = Unionfind(n+1)
friend = [{} for i in range(n+1)]
for i in range(m):
    a,b = inm()
    friend[a][b] = 1
    friend[b][a] = 1
    uf.conn(a,b)
blk = [{} for i in range(n+1)]
for i in range(k):
    a,b = inm()
    blk[a][b] = 1
    blk[b][a] = 1
gr = {}
for i in range(1,n+1):
    r = uf.root(i)
    if r in gr:
        gr[r] += 1
    else:
        gr[r] = 1
for i in range(1,n+1):
    r = uf.root(i)
    x = gr[r]-1
    for f in friend[i]:
        if uf.root(f)==r:
            x -= 1
    for f in blk[i]:
        if uf.root(f)==r:
            x -= 1
    printn(str(x)+' ')
print("")

Submission status: Accepted

Solution code:
import sys
from collections import deque


def main():
    n, m, k = map(int, input().split(" "))
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    count = [0] * n
    for _ in range(m):
        i, j = map(int, sys.stdin.readline().strip().split(" "))
        friends[i - 1].add(j)
        friends[j - 1].add(i)
        count[i - 1] += 1
        count[j - 1] += 1
    for _ in range(k):
        i, j = map(int, sys.stdin.readline().strip().split(" "))
        blocks[i - 1].add(j)
        blocks[j - 1].add(i)
    cluster_size = [-1] * n
    for i in range(n):
        if cluster_size[i] != -1:
            continue
        stack = deque()
        stack.append(friends[i])
        space = {i + 1}
        while len(stack) > 0:
            s = stack.pop()
            for v in s:
                if v not in space:
                    space.add(v)
                    stack.append(friends[v - 1])
        size = len(space)
        for v in space:
            block_in_cluster = len(space & blocks[v - 1])
            cluster_size[v - 1] = size - block_in_cluster
    ans = []
    for i in range(n):
        ans.append(str(cluster_size[i] - 1 - count[i]))
    print(" ".join(ans))


if __name__ == '__main__':
    main()

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 unite(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()}
n,m,k=map(int,input().split())
uf=UnionFind(n+1)
cnt=[0]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  uf.unite(a,b)
  cnt[a]+=1
  cnt[b]+=1
for i in range(k):
  c,d=map(int,input().split())
  if uf.same(c,d):
    cnt[c]+=1
    cnt[d]+=1
ans=[]
for i in range(1,n+1):
  ans.append(uf.size(i)-cnt[i]-1)
print(*ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline
n, m, k = map(int, readline().split())

friend = [set() for i in range(n)]
not_friend = [set() for i in range(n)]
for i in range(m):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
for i in range(k):
    c, d = map(int, readline().split())
    c -= 1
    d -= 1
    not_friend[c].add(d)
    not_friend[d].add(c)

suggest_friends = [-1] * n
for i in range(n):
    if suggest_friends[i] != -1:
        continue
    q = deque(friend[i])
    friend_group = set(friend[i])
    while q:
        p = q.popleft()
        for f in friend[p]:
            if not(f in friend_group):
                q.append(f)
                friend_group.add(f)
    num = len(friend_group)
    for f in friend_group:
        suggest_friends[f] = num - 1 - len(friend[f] | not_friend[f] & friend_group)

for i in range(n):
    if suggest_friends[i] == -1:
        suggest_friends[i] = 0
print(*suggest_friends)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque

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

friend = [set() for i in range(n)]
not_friend = [set() for i in range(n)]

suggest_friends = [-1] * n
for i in range(m):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
    # friend[b].append(a)
for i in range(k):
    c, d = map(int, readline().split())
    c -= 1
    d -= 1
    not_friend[c].add(d)
    not_friend[d].add(c)
    # not_friend[d].append(c)
for i in range(n):
    if suggest_friends[i] != -1:
        continue
    q = deque(friend[i])
    friend_group = set(friend[i])
    while q:
        p = q.popleft()
        for f in friend[p]:
            if not(f in friend_group):
                q.append(f)
                friend_group.add(f)
    num = len(friend_group)
    for f in friend_group:
        suggest_friends[f] = num - 1 - len(friend[f] | not_friend[f] & friend_group)

for i in range(n):
    if suggest_friends[i] == -1:
        suggest_friends[i] = 0
print(*suggest_friends)

Submission status: Accepted

Solution code:
class UnionFind():
    
    def __init__(self,size): 
        self.table = [-1 for _ in range(size)]
        self.cou = [1 for _ in range(size)]
        
    def find(self,x): 
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
        
    def union(self,x,y): 
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] > self.table[s2]:
                self.table[s1] = s2
                self.cou[s2] += self.cou[s1]
                self.cou[s1] = 0
            elif self.table[s2] > self.table[s1]:
                self.table[s2] = s1
                self.cou[s1] += self.cou[s2]
                self.cou[s2] = 0
            else:
                self.table[s2] = s1
                self.table[s1] -= 1
                self.cou[s1] += self.cou[s2]
                self.cou[s2] = 0
        return
    
n, m, k = map(int, input().split())
BList = [[] for _ in range(n)]
friendU = UnionFind(n)

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

for i in range(k):
    c, d = map(int, input().split())
    if friendU.find(c-1) == friendU.find(d-1):
        BList[c-1].append(d-1)
        BList[d-1].append(c-1)
    
ansl = []
for i in range(n):
    j = friendU.find(i)
    ans = friendU.cou[j] - len(BList[i]) - 1
    ansl.append(ans)

print(*ansl)

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

# -- Union Find
par = [i for i in range(N)]
rank = [0]*N

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

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

def unite(x, y):
    x, y = root(x), root(y)
    if x == y: return

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

# -- Union Find


block_num = [0]*N
friend_num = [0]*N
cls_cnt = {} # cluster count

for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    unite(a,b)


for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    if same(a,b):
        friend_num[a] += 1
        friend_num[b] += 1


for cd in CD:
    c, d = cd[0]-1, cd[1]-1
    if same(c,d):
        block_num[c] += 1
        block_num[d] += 1


cls_cnt = {} # cluster count
for i in range(N):
    r = root(i)
    if r in cls_cnt:
        cls_cnt[r] += 1
    else:
        cls_cnt[r] = 1


for i in range(N):
    r = root(i)
    ans = cls_cnt[r] - 1 - friend_num[i] - block_num[i]
    print(ans , end=' ')

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        else:
            if self.d[x] > self.d[y]:
                x, y = y, x
            self.d[x] += self.d[y]
            self.d[y] = x
            return True

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


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


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

for j in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d) == True:
        fb[c] += 1
        fb[d] += 1

for i in range(n):
    print(uf.size(i) - fb[i] - 1)

Submission status: Accepted

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

class UnionFindTree():
    def __init__(self, n):
        self.parent = [] # 親のノード
        self.rank = [] # 木の深さ
        self.number = [] # グループの要素数
        for i in range(n):
            self.parent.append(i)
            self.rank.append(0)
            self.number.append(1)

    # 根ノードを取得
    def find(self, 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 = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.number[y] += self.number[x]
        else:
            self.parent[y] = x
            self.number[x] += self.number[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じノードか判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # グループのノード数を取得
    def union_number(self, x):
        x = self.find(x)
        return self.number[x]

[N, M, K] = [int(i) for i in input().split()]

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

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

uf_tree = UnionFindTree(N)
for (a, b) in AB:
    a -= 1
    b -= 1
    uf_tree.unite(a, b)

# 友達候補を計算
candidates = []
for n in range(N):
    candidates.append(uf_tree.union_number(n) - 1)

# 友達を除外
for (a, b) in AB:
    a -= 1
    b -= 1
    candidates[a] -= 1
    candidates[b] -= 1

# ブロックユーザを除外
for (c, d) in CD:
    c -= 1
    d -= 1
    if uf_tree.same(c, d):
        candidates[c] -= 1
        candidates[d] -= 1

ans = ''
for candidate in candidates:
    ans += str(candidate) + ' '

print(ans[:len(ans) - 1])