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:
N,M,K = map(int,input().split())
Fri = [list(map(int,input().split())) for _ in range(M)]
Blo = [list(map(int,input().split())) for _ in range(K)]

#union-find
par = [i for i in range(N+1)]
relation = [1 for _ in range(N+1)] #自身を含む同グループの数
rank = [0 for _ in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x,y = find(x),find(y)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
            relation[y] += relation[x]
        else:
            par[y] = x
            relation[x] += relation[y]
            if rank[x] == rank[y]:
                rank[x] += 1

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

ans = [relation[find(i)] for i in range(N+1)]
for m in range(M):
    unite(Fri[m][0],Fri[m][1])
    ans[Fri[m][0]] -= 1
    ans[Fri[m][1]] -= 1

for k in range(K):
    if same(Blo[k][0],Blo[k][1]):
        ans[Blo[k][0]] -= 1
        ans[Blo[k][1]] -= 1

for i in range(1,N+1):
    ans[i] += (relation[find(i)] - 2)
    if i != 1:
        print(" ",end="")
    print(ans[i],end="")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(6500)

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]
d=[-1]*N

def find(n):
    if d[n]<0:
        return n
    else:
        return find(d[n])
def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def same(a,b):
    if find(a)==find(b):return True
    else:return False


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

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

ans=[0]*N
for i in range(N):
    p=find(i)
    ans[i]=-d[p]-len(F[i])-1
    for b in B[i]:
        if same(i,b):
            ans[i]-=1
for i in ans:
    print(str(i),end=" ")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)

class Uf():
    def __init__(self, n):
        self.par = [-1]*N
 
    def root(self, x):
        if self.par[x] < 0:
            return x
        
        root_x = self.root(self.par[x])
        self.par[x] = root_x
        return root_x
    
    def merge(self, a, b):
        a, b = self.root(a), self.root(b)
        
        if a == b:
            return
            
        if self.par[a] > self.par[b]:
            a, b = b, a
        
        self.par[a] += self.par[b]
        self.par[b] = a
                 
    def isSame(self, a, b):
        return self.root(a) == self.root(b)
    
    def size(self, x):
        return -self.par[self.root(x)]


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

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

uf = Uf(N)

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

for i in  range(K):
    a, b  = map(int,input().split())
    a, b = a-1, b-1
    if not uf.isSame(a,b):
        continue
    exep[a].append(b)
    exep[b].append(a)

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

Submission status: Accepted

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

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

u=UnionFind(n)
for i in range(m):
    a,b=ab[i]
    u.Unite(a,b)
l=[u.Count(i)-1 for i in range(n+1)]
for i in range(m):
    a,b=ab[i]
    l[a]-=1
    l[b]-=1
for i in range(k):
    c,d=cd[i]
    if u.isSameGroup(c,d):
        l[c]-=1
        l[d]-=1
print(*l[1:])

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline

    N, M, K=map(int, input().split())
    friend_or_block = [list() for _ in range(N)]
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.size(i) - len(friend_or_block[i]) - 1 for i in range(N)])

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline

    N, M, K=map(int, input().split())
    friend_or_block = [set() for _ in range(N)]
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.size(i) - len(friend_or_block[i]) - 1 for i in range(N)])

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline

    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.size(i) - friend_or_block[i] - 1 for i in range(N)])

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    class UnionFindTree:
        def __init__(self, n):
            self.parent = [-1] * n

        def find(self, x):
            p = self.parent
            while p[x] >= 0: x, p[x] = p[x], p[p[x]]
            return x

        def union(self, x, y):
            x, y, p = self.find(x), self.find(y), self.parent
            if x == y: return
            if p[x] > p[y]: x, y = y, x
            p[x], p[y] = p[x] + p[y], x

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

    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.size(i) - friend_or_block[i] - 1 for i in range(N)])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    class UnionFindTree:
        def __init__(self, n):
            self.parent = [-1] * n

        def root(self, x):
            p, s = self.parent[x], list()
            while p >= 0:
                s.append(x)
                x, p = p, self.parent[p]
            for c in s: self.parent[c] = x
            return x

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

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

        def unite(self, x, y):
            xr, yr = self.root(x), self.root(y)
            if xr == yr: return
            if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
            self.parent[xr] += self.parent[yr]
            self.parent[yr] = xr

    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])

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

    def root(self, x):
        p, s = self.parent[x], list()
        while p >= 0:
            s.append(x)
            x, p = p, self.parent[p]
        for c in s: self.parent[c] = x
        return x

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

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

    def unite(self, x, y):
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

if __name__ == '__main__':
    main()

Submission status: Accepted

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

par = [-1 for _ in range(n)]

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

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

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

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

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

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

for i in range(n):
    ans[i] += size(i)

print(*ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc157/submissions/10475457

import sys
readline = sys.stdin.readline

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

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

B = [[] for _ in range(N + 1)]
for _ in range(K):
    c, d = map(int, readline().split())
    B[c].append(d)
    B[d].append(c)

seen = [-1] * (N + 1)
group = 0


def dfs(graph, s):
    stack = [s]
    seen[s] = group
    n_connection = 1

    while stack:
        u = stack.pop()
        for v in graph[u]:
            if seen[v] == -1:
                n_connection += 1
                seen[v] = group
                stack.append(v)

    return n_connection


union = {}
for i in range(1, N + 1):
    if seen[i] == -1:
        n = dfs(F, i)
        union[group] = n
        group += 1

ans = []
for i in range(1, N + 1):
    tmp = 0
    tmp += union[seen[i]] - 1
    tmp -= len(F[i])
    for j in B[i]:
        if seen[j] == seen[i]:
            tmp -= 1
    ans.append(tmp)

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

Submission status: Accepted

Solution code:
r=lambda x:p[x]>0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=p[:]
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=y=x
 if x==y:s[a]-=1;s[b]-=1;m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Submission status: Accepted

Solution code:
import sys
sys.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)]

par = [n+1 for n in range(N)]
rank = [0 for _ in range(N)]
size = [1 for _ in range(N)]

# 木の根を求める
def find(x):
  if par[x-1] != x:
    par[x-1] = find(par[x-1])
  return par[x-1]
# x, y の属する集合を併合
def unite(x, y):
  rx = find(x)
  ry = find(y)
  if rx == ry:
    return
  if rank[rx-1] < rank[ry-1]:
    rx, ry = ry, rx
  par[ry-1] = rx
  size[rx-1] += size[ry-1]
  if rank[rx-1] == rank[ry-1]:
    rank[rx-1] += 1
# x, y が同じ集合に属するか否か
def same(x, y):
  return find(x) == find(y)
def getsize(x):
  return size[find(x)-1]

friends = [0 for _ in range(N)]
for A, B in AB:
  unite(A, B)
  friends[A-1] += 1
  friends[B-1] += 1

ans = [0 for _ in range(N)]

for n in range(N):
  ans[n] = getsize(n+1) - friends[n] -1

for C, D in CD:
  if same(C, D):
    ans[C-1] -= 1
    ans[D-1] -= 1
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
r=lambda x:p[x]>0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=p[:]
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=y=x
 if x==y:s[a]-=1;s[b]-=1
 m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Submission status: Accepted

Solution code:
r=lambda x:p[x]>0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=[-1]*-~n
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=x
 if(x==y)+(m>0):s[a]-=1;s[b]-=1
 m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, v: int):
        self.value = v
        self.size = 1
        self.depth = 1
        self.parent = None
        self.friends = set()
        self.blocked = 0

    def get_root(self):
        t = self
        while(t.parent != None):
            t = t.parent
        return t

    def merge(self, t):
        p, c = (self, t) if self.depth > t.depth else (t, self)
        c.parent = p
        p.depth = max(p.size, c.size + 1)
        p.size += c.size

def main():
    n, m, k = [int(s) for s in input().split()]
    forest = [Tree(i+1) for i in range(n)]

    for i in range(m):
        a, b = [int(s) for s in input().split()]
        ta, tb = forest[a-1], forest[b-1]
        ta.friends.add(b)
        tb.friends.add(a)
        ra = ta.get_root()
        rb = tb.get_root()
        if ra != rb:
            ra.merge(rb)

    roots = [t.get_root() for t in forest]
    for i in range(k):
        c, d = [int(s) for s in input().split()]
        tc, td = forest[c-1], forest[d-1]
        rc = roots[c-1]
        rd = roots[d-1]
        if rc == rd:
            tc.blocked +=1
            td.blocked +=1

    cands = []
    for t in forest:
        root = roots[t.value - 1]
        cand = root.size - len(t.friends) - t.blocked - 1
        cands.append(str(cand))
    print(" ".join(cands))

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.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 = []
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a - 1, b - 1)
    ab.append([a, b])

out = []
for x in range(N):
    out.append(uf.size(x)-1)
    # print(uf.size(x))

for x in ab:
    out[x[0] - 1] -= 1
    out[x[1] - 1] -= 1

cd = []
for _ in range(K):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        out[c - 1] -= 1
        out[d - 1] -= 1
print(" ".join(map(str, out)))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, frnd, blck = map(int, input().split())
    blst = [set() for i in range(n)]
    flst = [set() for i in range(n)]
    uf = UnionFind(n)
    for _ in range(frnd):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        flst[a].add(b)
        flst[b].add(a)
        uf.union(a, b)
    for _ in range(blck):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        blst[c].add(d)
        blst[d].add(c)
    for i in range(n):
        ans = uf.size(i) - len(flst[i]) - 1
        for v in blst[i]:
            if uf.same(i, v):
                ans -= 1
        print(ans, end="")
        if i < n:
            print(" ", end="")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:

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

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

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


N, M, K = map(int, input().split())
Frd, Blk = {i: [] for i in range(N)}, {i: [] for i in range(N)}

uni = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    uni.unite(A - 1, B - 1)
    Frd[A - 1].append(B - 1)
    Frd[B - 1].append(A - 1)
for _ in range(K):
    C, D = map(int, input().split())
    Blk[C - 1].append(D - 1)
    Blk[D - 1].append(C - 1)

ans = []
for i in range(N):
    nBlk = sum([1 for b in Blk[i] if uni.isSame(i, b)])
    ans.append(str(uni.size(i) - 1 - len(Frd[i]) - nBlk))
print(' '.join(ans))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.d = []
        for i in range(n):
            self.d.append(-1)
    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
        if self.d[x] > self.d[y]:
            y, x = x, y
        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())

dame = [set() for _ in range(n)]
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.unite(a, b)
    dame[a].add(b)
    dame[b].add(a)

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

for i in range(n):
    ans = uf.size(i) - 1
    ans -= len(dame[i])
    print(ans, end=" ")
print()

Submission status: Accepted

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

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])  # 経路圧縮
        return par[x]

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    # サイズの大きい木にサイズの小さい木をくっつける。親の直下に親をくっつける。
    # 親のサイズは負の値になっているので、符号に注意
    if par[x] < par[y]:
        par[x] += par[y]
        par[y] = x
    else:
        par[y] += par[x]
        par[x] = y
    return True

friends_num = [0] * 100005
for _ in range(m):
    num_from, num_to = map(int, input().split())
    num_from -= 1
    num_to -= 1
    friends_num[num_from] += 1
    friends_num[num_to] += 1
    unite(num_from, num_to)

blocks = [[] * n for i in range(n)]
for _ in range(k):
    num_from, num_to = map(int, input().split())
    num_from -= 1
    num_to -= 1
    blocks[num_from].append(num_to)
    blocks[num_to].append(num_from)

ans_list = []
for i in range(n):
    ans = -par[find(i)] - friends_num[i] - 1
    for b in blocks[i]:
        if same(i, b):
            ans -= 1
    ans_list.append(ans)

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

Submission status: Accepted

Solution code:
#import sys
#sys.setrecursionlimit(500000)　マージテクをちゃんとしていればこんなものはいらないはず……

class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

    def find(self,n):
        if self.parents[n] < 0:
            return n
        else:
            return self.find(self.parents[n])


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        #union by rank
        if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
            a_par,b_par = b_par,a_par
        if self.rnks[a_par] == self.rnks[b_par]:
            self.rnks[a_par] += 1
##        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
##            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.size(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


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






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#sys.setrecursionlimit(500000)　マージテクをちゃんとしていればこんなものはいらないはず……

class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

    def find(self,n):
        if self.parents[n] < 0:
            return n
        else:
            return self.find(self.parents[n])


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        ##union by rank
        #if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
        #    a_par,b_par = b_par,a_par
        #if self.rnks[a_par] == self.rnks[b_par]:
        #    self.rnks[a_par] += 1
        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.size(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


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






if __name__ == '__main__':
    main()