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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().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 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 = inpl()
uf = UnionFind(n)
fr = [[] for _ in range(n)]
frs = [set() for _ in range(n)]
bl = [[] for _ in range(n)]
for _ in range(m):
    a,b = inpl()
    a,b = a-1,b-1
    fr[a].append(b)
    fr[b].append(a)
    frs[a].add(b)
    frs[b].add(a)
    uf.union(a,b)
for _ in range(k):
    a,b = inpl()
    a,b = a-1,b-1
    bl[a].append(b)
    bl[b].append(a)

for i in range(n):
    re = 0
    for j in bl[i]:
        if uf.same(i,j) and not j in frs[i]:
            re += 1
    print(uf.size(i) - len(fr[i]) - re - 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())
uf = UnionFind(n)
friend = [set([]) for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai -= 1; bi -= 1
    uf.union(ai, bi)
    friend[ai].add(bi)
    friend[bi].add(ai)

block = [set([]) for i in range(n)]
for i in range(k):
    ci, di = map(int, input().split())
    ci -= 1; di -= 1
    block[ci].add(di)
    block[di].add(ci)

for i in range(n):
    uf.find(i)

ans = []
for i in range(n):
    num = uf.size(i) - len(friend[i]) - 1
    for j in block[i]:
        if uf.find(i) == uf.find(j):
            num -= 1
    ans.append(num)

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

Submission status: Accepted

Solution code:
from collections import deque

def dfs(start):
    S = deque([start])
    link = {start}
    VL[start] = 1
    while S:
        node = S.pop()
        for f in AB[node]:
            if VL[f] == 1:
                continue
            link.add(f)
            S.append(f)
            VL[f] = 1
    for l in link:
        res[l] = len(link) - len(link & AB[l]) - len(link & CD[l]) - 1

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

AB = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB[a].add(b)
    AB[b].add(a)

CD = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    CD[c].add(d)
    CD[d].add(c)

VL = [0] * N
res = [0] * N

for i in range(N):
    if VL[i] == 0:
        dfs(i)

print(*res)

Submission status: Accepted

Solution code:
def find(i):
    x = i
    while x!=G[x][0]:
        x = G[x][0]
    return x
def union(i,j):
    ai = find(i)
    ni = G[ai][1]
    aj = find(j)
    nj = G[aj][1]
    if ai!=aj:
        if ni>=nj:
            G[aj][0] = ai
            if G[aj][1]==G[ai][1]:
                G[ai][1] += 1
            G[ai][2] += G[aj][2]
        else:
            G[ai][0] = aj
            G[aj][2] += G[ai][2]
N,M,K = map(int,input().split())
G = {i:[i,0,1] for i in range(1,N+1)}
A = {i:[] for i in range(1,N+1)}
B = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    union(a,b)
    A[a].append(b)
    A[b].append(a)
for _ in range(K):
    c,d = map(int,input().split())
    B[c].append(d)
    B[d].append(c)
C = []
for i in range(1,N+1):
    ai = find(i)
    n = G[ai][2]
    m = len(A[i])
    k = 0
    for j in B[i]:
        if ai==find(j):
            k += 1
    n = n-m-k
    C.append(n-1)
print(*C)

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

Submission status: Accepted

Solution code:
def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

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

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

import sys
input = sys.stdin.readline

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

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

C = [0]*n

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    C[a] += 1
    C[b] += 1
    Unite(a, b, par, rank)

ans = [0]*n
for i in range(n):
    ans[i] = Size(i, par)-1-C[i]

for i in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if Same(c, d, par):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
A = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    A[a].append(b)
    A[b].append(a)
C = [[] for i in range(n+1)]
for i in range(k):
    c,d = map(int,input().split())
    C[c].append(d)
    C[d].append(c)
from collections import deque
reach = [0]*(n+1)
for i in range(1,n+1):
    if reach[i] != 0:
        pass
    else:
        reach[i] = i
        q = deque([])
        q.append(i)
        while q:
            x = q.popleft()
            for s in A[x]:
                if reach[s] == 0:
                    q.append(s)
                    reach[s] = i
dis_count = [0]*(n+1)
for i,C0 in enumerate(C):
    for CC in C0:
        if reach[CC] == reach[i]:
            dis_count[i] += 1
import collections
D = collections.Counter(reach)
for i in range(1,n+1):
    print(D[reach[i]]-len(A[i])-dis_count[i]-1,end="")
    print(" ",end="")
print("")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())

friend = [0] * n
block = [0] * n

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

uf = UnionFind(n)
ab = [list(map(int, input().split())) for i in range(m)]
for a, b in ab:
    uf.union(a-1, b-1)
    friend[a-1]+=1
    friend[b-1]+=1

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

ans = []
for i in range(n):
    ans.append(uf.size(i) - friend[i] - block[i] -1 )
print(' '.join(list(map(str, ans))))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m,k = map(int, input().split())
class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        if i==j:
            return
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
    
uf = UnionFindTree(n)
ns = [[] for _ in range(n)]
for i in range(m):
    a,b = map(lambda x: int(x)-1, input().split())
    uf.connect(a,b)
    ns[a].append(b)
    ns[b].append(a)

for i in range(k):
    c,d = map(lambda x: int(x)-1, input().split())
    ns[c].append(d)
    ns[d].append(c)
    
ans = [None]*n
for i in range(n):
    r = uf.root(i)
    s = uf.size[r]
    v = 0
    for j in ns[i]:
        if r==uf.root(j):
            v += 1
    ans[i] = s - v - 1
write(" ".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

def graph_input(N, M):
    G = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b = map(int, readline().split())
        G[a].append(b)
        G[b].append(a)
    return G

N, M, K = map(int, readline().split())
friend = graph_input(N, M)
block = graph_input(N, K)

uf = UnionFind(N + 1)
for a in range(N + 1):
    for b in friend[a]:
        uf.merge(a, b)

answer = [0] * (N + 1)
for a in range(N + 1):
    n = uf.size[uf[a]] - 1
    for x in friend[a] + block[a]:
        if uf[a] == uf[x]:
            n -= 1
    answer[a] = n

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

Submission status: Accepted

Solution code:
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, input().split())
ins_friend = UnionFind(N)
friends = [0 for i in range(N)]
blocks = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    ins_friend.union(a-1, b-1)
    friends[a-1] += 1
    friends[b-1] += 1
for _ in range(K):
    c, d = map(int, input().split())
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)
ans = [0 for i in range(N)]
for i in range(N):
    ans[i] = ins_friend.count(i) - 1 - friends[i]
    for x in blocks[i]:
        if ins_friend.find(i, x) == True:
            ans[i] -= 1
print(*ans)

Submission status: Accepted

Solution code:
# 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())

N, M, K = map(int, input().split())
par = [-1]*N
#直接友達になっている人数とブロックしている人数をカウント
num = [0]*N

uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    #友達関係をつなげる
    uf.union(a, b)
    #直接友達なのでカウントする
    num[a] += 1
    num[b] += 1

for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    # print(f"c{c}, d{d}, uf.same(c, d) {uf.same(c, d)}")
    #同じグループに属している場合、size()にカウントされるのでnumを増やす
    if uf.same(c, d):
        num[c] += 1
        num[d] += 1
# print(num)
for i in range(N):
    #直接友達関係の人と同じグループでブロックしている人、自分自身を除く人数が候補となる
    print(uf.size(i)-1-num[i], end=" ")

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
def main():
    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)]

    n, m, k = map(int, input().split())
    par = [-1] * n
    r = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        r[a] -= 1
        r[b] -= 1
    for i1 in range(n):
        r[i1] += size(i1)
    m = map(int, read().split())
    cd = zip(m, m)
    for c, d in cd:
        c -= 1
        d -= 1
        if same(c, d):
            r[c] -= 1
            r[d] -= 1
    print(*r, end=' ')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Union Find 木
from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 6)


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

parent = [-1] * N
friends = [[] for _ in range(N)]
for A, B in AB:
    unite(parent, A - 1, B - 1)
    friends[A-1].append(B-1)
    friends[B-1].append(A-1)
blocks = [[] for _ in range(N)]
for C, D in CD:
    blocks[C-1].append(D-1)
    blocks[D-1].append(C-1)

result = []
for i in range(N):
    p = find(parent, i)
    t = -parent[p] - 1
    t -= len(friends[i])
    for b in blocks[i]:
        if p == find(parent, b):
            t -= 1
    result.append(t)
print(*result)

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    N, M, K = map(int, input().split())
    f = [set() for _ in range(N + 1)]
    b = [set() for _ in range(N + 1)]

    for _ in range(M):
        i, j = map(int, input().split())
        f[i].add(j)
        f[j].add(i)
    for _ in range(K):
        i, j = map(int, input().split())
        b[i].add(j)
        b[j].add(i)
    
    visited = [False] * (N + 1)
    ans = [0] * (N + 1)

    for i in range(1, N+1):
        if visited[i]:
            continue
        visited[i] = True
        link = {i}
        todo = deque([i])
        while len(todo) != 0:
            c = todo.pop()
            for p in f[c]:
                if not(visited[p]):
                    link.add(p)
                    todo.append(p)
                    visited[p] = True
        for j in link:
            ans[j] = len(link) - len(link & f[j]) - len(link & b[j]) - 1
    
    print(*ans[1:])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N,M,K=map(int,input().split())
    ABadj=[[] for i in range(N)]
    CDadj=[set() for i in range(N)]
    for i in range(M):
        a,b=map(int,input().split())
        ABadj[a-1].append(b-1)
        ABadj[b-1].append(a-1)
    for i in range(K):
        c,d=map(int,input().split())
        CDadj[c-1].add(d-1)
        CDadj[d-1].add(c-1)
    
    w=[-1]*N
    sets=[]
    j=-1
    done=[-1]*N
    for i in range(N):
        if done[i]==-1:
            sets.append(set())
            j+=1
            qu=deque([i])
            done[i]=1
            sets[j].add(i)
            w[i]=j
            while(len(qu)>0):
                v=qu.popleft()
                for nv in ABadj[v]:
                    if done[nv]==-1:
                        done[nv]=1
                        qu.append(nv)
                        sets[j].add(nv)
                        w[nv]=j
    
    for i in range(N):
        ans=len(sets[w[i]])-1-len(ABadj[i])
        for bl in CDadj[i]:
            if bl in sets[w[i]]:
                ans-=1
        print(ans,end=" ")
            
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# 4 4 1
# 2 1
# 1 3
# 3 2
# 3 4
# 4 1

inp = input
MAXX = 10**5 + 5

def bfs(NN, adj, visited, node, comp, ncomp):
    compsize = 0
    while len(node) > 0:
        newnode = []
        for n in node:
            comp[n] = ncomp
            compsize += 1
            for a in adj[n]:
                if visited[a] == False:
                    visited[a] = True
                    newnode.append(a)
        node = newnode

    return compsize


###############################
N, M, K = map(int, inp().split())
adj = [[] for _ in range(N+1)]
nfriend = [0]*(N+1)
nblock = [0]*(N+1)
for m in range(M):
    a, b, = map(int, inp().split())
    adj[a].append(b)
    adj[b].append(a)
    nfriend[a] += 1
    nfriend[b] += 1

comp = [0]*(N+1)
compsize = [0]
ncomp = 0
visited = [False]*(N+1)

for n in range(1, N+1):
    if comp[n] <= 0:
        visited[n] = True
        csize = bfs(N, adj, visited, [n], comp, ncomp+1)
        if csize > 0:
            ncomp += 1
            compsize.append(csize)

for k in range(K):
    c, d = map(int, inp().split())
    if comp[c] == comp[d]:
        nblock[c] += 1
        nblock[d] += 1

ans = ""
for n in range(1, N+1):
    can = compsize[comp[n]] - nfriend[n] - nblock[n] - 1
    ans += str(can)
    if n == N:
        ans += "\n"
    else:
        ans += " "

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    # 連結成分の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]


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

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

    res = []
    for i in range(n):
        res.append(uf.size(i) - (len(edge[i]) + 1) - (len(block[i])))
    print(*res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
class Union_Find():
    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())

A=[set() for _ in range(N+1)]
U=Union_Find(N+1)
for _ in range(M):
    a,b=map(int,input().split())
    A[a].add(b)
    A[b].add(a)
    U.union(a,b)

C=[set() for _ in range(N+1)]
for _ in range(K):
    c,d=map(int,input().split())
    C[c].add(d)
    C[d].add(c)

S=[]
for k in range(1,N+1):
    t=U.size(k)
    for a in C[k]:
        if U.find(a)==U.find(k):
            t-=1

    t-=len(A[k])
    S.append(t-1)

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

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

ndic = {i:set() for i in range(1,N+1)}
bdic = {i:set() for i in range(1,N+1)}

uf = UnionFind(N+1)
rlt = []

for _ in range(M):
  a,b = map(int, input().split())
  ndic[a].add(b)
  ndic[b].add(a)
  uf.union(a,b)
  
for _ in range(K):
  a,b = map(int, input().split())
  bdic[a].add(b)
  bdic[b].add(a)
  
for i in range(1,N+1):
  tmp = uf.size(i)
  for a in bdic[i]:
    if uf.find(a) == uf.find(i):
      tmp -= 1
  tmp -= len(ndic[i])
  rlt.append(tmp-1)
  
print(" ".join(map(str, rlt)))

Submission status: Accepted

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

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.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 union(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 = map(int, input().split())


uf = UnionFind(n)

friends = [0] * (n + 1)
chain = [0] * (n + 1)

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

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

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

print(*ans)