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: Time Limit Exceeded

Solution code:
n,m,k=[int(x) for x in input().split()]

friends=[[] for y in range(n)]
blocks=[[0 for x in range(n)] for y in range(n)]
for i in range(m):
    a,b=[int(x) -1 for x in input().split()]
    friends[a].append(b)
    friends[b].append(a)
for i in range(k):
    c,d=[int(x)-1 for x in input().split()]
    blocks[c][d]=1
    blocks[d][c]=1
from collections import deque
ans=[0]*n
for a in range(n):
    for b in range(a+1,n):
        if b in friends[a] or blocks[a][b]==1:
            continue
        d=deque()
        d.append(a)
        flag=False
        searched=[0]*n
        searched[a]=1
        while d:
            tmp=d.popleft()
            searched[tmp]=1
            if tmp==b:
                flag=True
                break
            else:
                for friend in friends[tmp]:
                    if searched[friend]==1:
                        continue
                    d.append(friend)
        if flag:
            ans[a]+=1
            ans[b]+=1
print(" ".join([str(x) for x in ans]))

Submission status: Time Limit Exceeded

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)
d = [0 for i in range(N+1)]
F = []
B = [[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    uf.union(a,b)
    d[a] -= 1
    d[b] -= 1
for i in range(1,N+1):
    n = len(uf.members(i))
    d[i] += n - 1
for j in range(K):
    a,b = map(int,input().split())
    if uf.same(a,b):
        d[a] -= 1
        d[b] -= 1
d.pop(0)
for i in range(N):
    d[i] = str(d[i])
d = ' '.join(d)
print(d)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  while a != pre[a]:
    a = pre[a]
    A.append(a)
  while b != pre[b]:
    b = pre[b]
    B.append(b)
  #print(a,b)
  if a != b:
    pre[b] = a
    for aa in A:
      pre[aa] = a
    for bb in B:
      pre[bb] = a
root = []
cnt = [0 for _ in range(n)]
for i in range(n):
  I = int(i)
  while I != pre[I]:
    I = pre[I]
  root.append(I)
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.size = [1 for _ in range(size)]

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
      
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]
N, M, K = map(int, input().split())
U = UnionFind(N)
count = [0]*N
for _ in range(M):
    a, b = map(int, input().split())
    count[a-1]+=1
    count[b-1]+=1
    U.unite(a-1, b-1)
block = [[] for _ in range(N)]
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):
    cnt = U.get_size(i)-1-count[i]
    for b in block[i]:
        if U.same(i, b):
            cnt-=1
    ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] < 0: return x
    return self.root(self.T[x])

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

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True

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


N, M, K = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uni = Union(N)
f = [0] * N
for a, b in AB:
  a -= 1
  b -= 1
  uni.merge(a, b)
  f[a] += 1
  f[b] += 1

L = [[] for _ in range(N)]
for c, d in CD:
  c -= 1
  d -= 1
  L[c].append(d)
  L[d].append(c)

ans = [0] * N

for i in range(N):
  k = uni.size(i)
  k -= f[i] + 1
  for j in L[i]:
    if uni.same(i, j):
      k -= 1
  ans[i] = k

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
sys.setrecursionlimit(10 ** 6)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [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 unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0

		return

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

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

friend = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	friend[a-1].append(b-1)
	friend[b-1].append(a-1)
	uf.unite(a-1, b-1)

block = [[] for _ in range(n)]
for _ in range(k):
	a, b = map(int, input().split())
	block[a-1].append(b-1)
	block[b-1].append(a-1)

ans = []
for i in range(n):
	res = uf.get_size(i) - 1 - len(friend[i])
	for v in block[i]:
		if uf.find(i) == uf.find(v):
			res -= 1
	ans.append(res)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10 ** 6)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [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 unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0

		return

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

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

friend = [[] for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	friend[a-1].append(b-1)
	friend[b-1].append(a-1)
	uf.unite(a-1, b-1)

block = [[] for _ in range(n)]
for _ in range(k):
	a, b = map(int, input().split())
	block[a-1].append(b-1)
	block[b-1].append(a-1)

ans = []
for i in range(n):
	res = uf.get_size(i) - 1 - len(friend[i])
	for v in block[i]:
		if uf.find(i) == uf.find(v):
			res -= 1
	ans.append(res)

print(*ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1 << 30)

nv, ne, nBad = map(int, input().split())
g = [[] for _ in range(nv)]
for _ in range(ne):
    u, v = map(lambda x: int(x) - 1, input().split())
    g[u].append(v)
    g[v].append(u)
a = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(nBad)]

def dfs(v):
    id[v] = cur
    comps[-1].append(v)
    for to in g[v]:
        if id[to] == None:
            dfs(to)

id = [None] * nv
cur = 0
comps = []
for v in range(nv):
    if id[v] == None:
        comps.append([])
        dfs(v)
        cur += 1
bad = [0] * nv
for u, v in a:
    if id[u] == id[v]:
        bad[u] += 1
        bad[v] += 1
ret = [None] * nv
for v in range(nv):
    ret[v] = len(comps[id[v]]) - 1 - len(g[v]) - bad[v]
print(' '.join(map(str, ret)))

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.n = n
    self.g = [i for i in range(n)]
    self.nmembers = [1 for i in range(n)]
  def __len__(self):
    return self.n
  def __str__(self):
    return "group:{}\nnmembers:{}".format(self.g,self.nmembers)
  def __getitem__(self,x):
    return self.whichgroup(x)
  def merge(self, x, y):
    gx = self.whichgroup(x)
    gy = self.whichgroup(y)
    if gx != gy:
      nx = self.nmembers[gx]
      ny = self.nmembers[gy]
      ming = min(gx, gy)
      maxg = gx + gy - ming
      self.g[maxg] = ming
      self.nmembers[maxg] = 0
      self.nmembers[ming] = nx + ny
    
  def whichgroup(self, x):
    if x != self.g[x]:
      self.g[x] = self.whichgroup(self.g[x])
      self.nmembers[x] = 0
      return self.g[x]
    else:
      return x

N, M, K = map(int, input().split())
UF = UnionFind(N)
F = [0 for i in range(N)]
B = [0 for i in range(N)]
#print(UF)
for i in range(M):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  #print("x:{}, y:{}".format(x, y))
  UF.merge(x, y)
  F[x] += 1
  F[y] += 1
for i in range(K):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  
  gx = UF.whichgroup(x)
  gy = UF.whichgroup(y)
  if gx == gy:
    B[x] += 1
    B[y] += 1
#print(UF)
ans = []
for i in range(N):
  ans.append(UF.nmembers[UF[i]]-B[i]-F[i]-1)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M, K = map(int, input().split())

flst = []
blst = []
glooplst = [i for i in range(N+1)]
colorlst = [0]*(N+1)
countlst = [0]*(N+1)
anslst = [0]*(N+1)
d = deque()

for i in range(N+1):
    flst.append([])
    blst.append([])


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


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


for i in range(1, N+1):
    if colorlst[i] == 0:
        d.append(i)
        colorlst[i] = 1
        countlst[i] += 1
        while d:
            now = d.popleft()
            for j in flst[now]:
                if colorlst[j] == 0:
                    d.append(j)
                    colorlst[j] = 1
                    glooplst[j] = i
                    countlst[i] += 1

for i in range(1, N+1):
    cnt = countlst[glooplst[i]] - len(flst[i]) -1
    for j in blst[i]:
        if glooplst[i] == glooplst[j]:
            cnt -= 1

    print(cnt, end=' ')

print()

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())

class MergeFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
        # self.lista = [[_] for _ in range(n)]

    def find(self, a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]

    def merge(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        # self.lista[a] += self.lista[b]
        # self.lista[b] = []

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets

n,m,k=sep()
d=MergeFind(n)
temp=[]
for _ in range(m):
    a,b=sep()
    a -= 1
    b -= 1
    temp.append((a,b))
    d.merge(a,b)
ans=[0]*n
for i in range(n):
    ans[i]=d.set_size(i)-1
for _ in range(k):
    a, b = sep()
    a -= 1
    b -= 1
    temp.append((a, b))
for i in temp:
    a,b=i
    if d.find(a)==d.find(b):
        ans[a]-=1
        ans[b]-=1
print(*ans)

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    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)
f = [0 for _ in range(N)]
n = [0 for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    
    f[a] += 1
    f[b] += 1
    
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if(uf.same(c, d)):
        n[c] += 1
        n[d] += 1
    
ans = []
for i in range(N):
    ans.append(uf.size(i)-f[i]-n[i]-1)
    
print(*ans)

Submission status: Accepted

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

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

    def unite(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u == v:
            return

        if self.parents[u] > self.parents[v]:
            u, v = v, u

        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):
        return -self.parents[self.find(v)]

    def same(self, u, v):
        return self.find(u) == self.find(v)

N, M, K = map(int, input().split())
uf = UnionFind(N+1)
F = [0] * (N+1)
B = [0] * (N+1)
for _ in range(M):
    a, b = map(int, input().split())
    uf.unite(a, b)
    F[a] += 1
    F[b] += 1

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

for i in range(1, N+1):
    ans = uf.size(i) - F[i] - B[i] - 1
    print(ans, end=' ')

print()

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
import collections
par = []
for i in range(n):
    par.append(i)  #初期親
rank = [1 for i in range(n)] #初期ランク
flist = [[] for i in range(n)]
blist = [[] for i in range(n)]
cut = []
def find(n): #親検索andランク短縮
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
        return n
    else:
        cut.append(n)
        find(par[n])
        return find(par[n])
def shorten(n): # ランクを2にする
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
    else:
        cut.append(n)
        shorten(par[n])
def unite(a,b): #グループ併合
    x = find(a)
    y = find(b) #根っこ同士をくっつける
    if x == y: 
        return    #既に同一ユニオンなら何もしない
    if rank[x] < rank[y]:
        par[x] = y 
    elif rank[x] == rank[y]:
        par[y] = x
        rank[x] += 1
    else:
        par[y] = x
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    flist[a].append(b)
    flist[b].append(a)
    unite(a,b)
for i in range(n):
    shorten(i)
for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if par[a] == par[b]:
        blist[a].append(b)
        blist[b].append(a)
c = collections.Counter(par)
for i in range(n):
    ans = c[par[i]] -len(flist[i])-len(blist[i])-1
    print(ans,end = ' ')

Submission status: Accepted

Solution code:
from _collections import deque
n,m,k=map(int,input().split())
import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

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

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]

x=[-1]*(n+1)

def s(y):
    global i
    if x[y]>0:
        return
    x[y]=i
    for j in fre[y]:
        if x[j]==-1:
            s(j)

for i in range(1,n+1):
    s(i)

g=[0]*(n+1)
for i in range(1,n+1):
    g[x[i]]+=1
for i in range(1,n+1):
    g[i]=g[x[i]]

for i in range(1,n+1):
    aa=g[i]-1
    aa-=len(fre[i])
    for j in bro[i]:
        if x[i]==x[j]:
            aa-=1
    ans.append(str(aa))
print(" ".join(ans))

Submission status: Accepted

Solution code:
from _collections import deque
n,m,k=map(int,input().split())
import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

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

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]

x=[-1]*(n+1)

def s(z,y):
    if x[y]>0:
        return
    x[y]=z
    for i in fre[y]:
        if x[i]==-1:
            s(z,i)

for i in range(1,n+1):
    s(i,i)

g=[0]*(n+1)
for i in range(1,n+1):
    g[x[i]]+=1
for i in range(1,n+1):
    g[i]=g[x[i]]

for i in range(1,n+1):
    aa=g[i]-1
    aa-=len(fre[i])
    for j in bro[i]:
        if x[i]==x[j]:
            aa-=1
    ans.append(str(aa))
print(" ".join(ans))

Submission status: Accepted

Solution code:
from _collections import deque
n,m,k=map(int,input().split())

fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

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

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]

x=[-1]*(n+1)

for i in range(1,n+1):
    if x[i]==-1:
        x[i]=i
        data=deque([i])
        while len(data)>0:
            p=data.popleft()
            for j in fre[p]:
                if x[j]==-1:
                    x[j]=i
                    data.append(j)
g=[0]*(n+1)
for i in range(1,n+1):
    g[x[i]]+=1
for i in range(1,n+1):
    g[i]=g[x[i]]

for i in range(1,n+1):
    aa=g[i]-1
    aa-=len(fre[i])
    for j in bro[i]:
        if x[i]==x[j]:
            aa-=1
    ans.append(str(aa))
print(" ".join(ans))

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x


fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    unite(a,b)
    fre[a].append(b)
    fre[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]
for i in range(1,n+1):
    anser=-root[r(i)]-1
    anser-=len(fre[i])
    for j in bro[i]:
        if r(i)==r(j):
            anser-=1
    ans.append(str(anser))
print(" ".join(ans))

Submission status: Accepted

Solution code:
def LI():
    return list(map(int, input().split()))


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 = LI()
par = [-1]*N
not_kouho = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
    not_kouho[a-1].append(b-1)
    not_kouho[b-1].append(a-1)

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

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = [-1]*n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.root(self.parents[x])
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            if x > y:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            return

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

u = UnionFind(n)
f = [set() for _ in range(n)]
l = [set() for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    f[a].add(b)
    f[b].add(a)
    u.unite(a, b)
for c, d in cd:
    c, d = c-1, d-1
    l[c].add(d)
    l[d].add(c)
ans = [0] * n
for i in range(n):
    r = u.root(i)
    bl = 0
    for j in l[i]:
        if u.root(j) == r:
            bl += 1
    ans[i] = -u.parents[r] - len(f[i]) - bl - 1
print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class UnionFind:
        def __init__(self, N: int):
            """
            N:要素数
            root:各要素の親要素の番号を格納するリスト.
                 ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
            rank:ランク
            """
            self.N = N
            self.root = [-1] * N
            self.rank = [0] * N

        def __repr__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

        def find(self, x: int) -> int:
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                while self.root[x] >= 0:
                    x = self.root[x]
                return x

        def union(self, x: int, y: int) -> int:
            """x,yが属する木をunion"""
            # 根を比較する
            # すでに同じ木に属していた場合は何もしない.
            # 違う木に属していた場合はrankを見てくっつける方を決める.
            # rankが同じ時はrankを1増やす
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return
            elif self.rank[x] > self.rank[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rank[x] == self.rank[y]:
                    self.rank[y] += 1

        def same(self, x: int, y: int) -> bool:
            """xとyが同じグループに属するかどうか"""
            return self.find(x) == self.find(y)

        def count(self, x):
            """頂点xが属する木のサイズを返す"""
            return - self.root[self.find(x)]

        def members(self, x):
            """xが属する木の要素を列挙"""
            _root = self.find(x)
            return [i for i in range(self.N) if self.find == _root]

        def roots(self):
            """森の根を列挙"""
            return [i for i, x in enumerate(self.root) 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=MI()
    uf=UnionFind(N)
    F=[0]*N
    B=[0]*N
    
    for i in range(M):
        a,b=MI()
        a-=1
        b-=1
        F[a]+=1
        F[b]+=1
        uf.union(a,b)
        
    for i in range(K):
        a,b=MI()
        a-=1
        b-=1
        if uf.same(a,b):
            B[a]+=1
            B[b]+=1
        
    ans=[]
    for i in range(N):
        aaa=uf.count(i)-1
        aaa-=F[i]+B[i]
        ans.append(aaa)
        

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

main()

Submission status: Accepted

Solution code:
from collections import deque
N,M,K = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
col = [-1 for _ in range(N+1)]
cnt = 0
for i in range(1,N+1):
    if col[i]<0:
        col[i] = cnt
        que = deque([i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if col[y]<0:
                    col[y] = cnt
                    que.append(y)
        cnt += 1
C = {}
for i in range(1,N+1):
    c = col[i]
    if c not in C:
        C[c] = 0
    C[c] += 1
B = {i:[] for i in range(1,N+1)}
for _ in range(K):
    c,d = map(int,input().split())
    B[c].append(d)
    B[d].append(c)
A = []
for i in range(1,N+1):
    c = col[i]
    cnt = C[c]-len(G[i])-1
    for y in B[i]:
        if col[y]==c:
            cnt -= 1
    A.append(cnt)
print(*A)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, K = mapint()

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

uf = UnionFind(N)
blocks = set()
friends = [0]*N
possi = [0]*N
for _ in range(M):
    a, b = mapint()
    uf.union(a-1, b-1)
    friends[a-1] += 1
    friends[b-1] += 1
for _ in range(K):
    a, b = mapint()
    if uf.same(a-1, b-1):
        friends[a-1] += 1
        friends[b-1] += 1
for i in range(N):
    possi[i] = uf.size(i)-friends[i]-1
print(*possi)