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())
table = [-1]*N
def union(x, y):
    global table
    x, y = find(x), find(y)
    if x==y:
        return False
    else:
        if table[x]>table[y]:
            x, y = y, x
        table[x] += table[y]
        table[y] = x
        return True
def find(x):
    if table[x]<0:
        return x
    else:
        table[x] = find(table[x])
        return table[x]
def rank(x):
    return table[find(x)]
friend = [[] for _ in range(N)]
block = [[] 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)
    union(a-1, b-1)

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

ans = [""]*N
for i in range(N):
    tmp = abs(rank(i)) - len(friend[i]) - 1
    cnt = 0
    for b in block[i]:
        if find(i)==find(b):
            cnt += 1
    ans[i] = str(tmp - cnt)
print(" ".join(ans))

Submission status: Accepted

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

table = [-1]*N
def union(x, y):
    global table
    x, y = find(x), find(y)
    if x==y:
        return False
    else:
        if table[x]>table[y]:
            x, y = y, x
        table[x] += table[y]
        table[y] = x
        return True

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

def rank(x):
    return table[find(x)]

friend = [[] for _ in range(N)]
block = [[] 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)
    union(a-1, b-1)

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

ans = [""]*N
for i in range(N):
    tmp = abs(rank(i)) - len(friend[i]) - 1
    cnt = 0
    for b in block[i]:
        if find(i)==find(b):
            cnt += 1
    ans[i] = str(tmp - cnt)
print(" ".join(ans))

Submission status: Accepted

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

from collections import deque
label=[-1]*n

i=0
for start in range(n):
    if label[start]!=-1:
        continue
    else:
        i+=1
        label[start]=i    
    f=deque([start])
    while f:
        v=f.popleft()        
        for e in edge[v]:
            if label[e]==-1:
                label[e]=i
                f.append(e)   

Renketsu=[0]*(n+1)

for i in label:
    Renketsu[i]+=1

Block=[0]*n
for _ in range(k):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if label[c]==label[d]:
        Block[c]+=1
        Block[d]+=1

ans=[]
for k in range(n):
    ans.append(Renketsu[label[k]]-1 - len(edge[k]) - Block[k])
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import Counter


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

graph1 = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x) - 1 for x in input().split()]
    graph1[a].append(b); graph1[b].append(a)

graph2 = [[] for _ in range(n)]
for _ in range(k):
    c, d = [int(x) - 1 for x in input().split()]
    graph2[c].append(d); graph2[d].append(c)

def dfs(now):
    X[now] = x
    for next in graph1[now]:
        if X[next]:
            continue
        dfs(next)

X = [0] * n
x = 1
for i in range(n):
    if X[i]:
        continue
    dfs(i)
    x += 1

cnt = Counter(X)

ans = []
for i in range(n):
    x = X[i]
    tmp = cnt[x] - 1
    tmp -= len(graph1[i])
    tmp -= sum(X[j] == x for j in graph2[i])
    ans.append(tmp)

print(*ans)

Submission status: Accepted

Solution code:
def main():
    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 other_members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root and i != x]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

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

    import sys
    def input():
        return sys.stdin.readline().rstrip()
    n, m, k = list(map(int, input().split()))
    uf = UnionFind(n)
    counts = [0] * n
    for _ in range(m):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        uf.union(a, b)
        counts[a] += 1
        counts[b] += 1
    for _ in range(k):
        c, d = list(map(lambda x: int(x) - 1, input().split()))
        if uf.same(c, d):
            counts[c] += 1
            counts[d] += 1
    print(' '.join([str(uf.size(i) - counts[i] - 1) for i in range(n)]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#create date: 2020-07-03 14:00

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

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 = na()
    par = [-1] * n
    friend = [0] * n
    block = [list() for i in range(n)]
    for i in range(m):
        a, b = na()
        a -= 1; b -= 1
        unite(a, b)
        friend[a] += 1
        friend[b] += 1
    for i in range(k):
        c, d = na()
        c -= 1; d -= 1
        block[c].append(d)
        block[d].append(c)
    #print(par, fb)
    for i in range(n):
        ans = size(i) - friend[i] - 1
        for b in block[i]:
            if same(i, b):
                ans -= 1
        print(ans, end=" ")
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
ab = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
cd = [set([]) for i in range(n)]
for i in range(k):
    c,d = map(int,input().split())
    cd[c-1].add(d-1)
    cd[d-1].add(c-1)
    
ans = [0 for i in range(n)]
data = [0 for i in range(n)] #見たら1
for i in range(n): #自分がi
    if(data[i] != 0): #もう見てたら必要なし
        continue
    data[i] = 1 #iの人を見る
    data2 = ab[i] + [i]
    data2 = set(data2)
    for j in ab[i]:
        data[j] = 1
    new_friends = [ab[i]]
    for fris in new_friends:
        new = [] #次の深さのリスト
        for fri in fris: #この層の友人を１人選ぶ
            for frfr in ab[fri]: #その友人の友人
                if(data[frfr] == 0): #見てなかったら加える
                    data[frfr] = 1 
                    new.append(frfr) #次の深さのリストに足す
                    data2.add(frfr) #グラフに足す
        if(len(new)==0):
            break
        else:
            new_friends.append(new)

    sam = len(data2)
    for j in data2:
        count = sam
        ans[j] = count - len(ab[j]) - len(cd[j] & data2) - 1 #自分と友達を除く


print(*ans)

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)
remove = [0]*(N+1)

for i in range(M):
    A,B=map(int,input().split())
    uf.union(A,B)
    remove[A] +=1
    remove[B] +=1

for i in range(K):
    A,B=map(int,input().split())
    if uf.same(A,B):
        remove[A] +=1
        remove[B] +=1

ANS = [0]*(N+1)

for i in range(0,N+1):
    ANS[i] = uf.size(i) - remove[i] - 1

ANS.pop(0)
print(*ANS)

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)
Fr = [set() for _ in range(N)]

for _ in range(M):
  A, B = map(lambda x: int(x)-1, input().split())
  uf.union(A, B)
  Fr[A].add(B)
  Fr[B].add(A)

ans = []

for i in range(N):
  ans.append(uf.size(i) - len(Fr[i]) - 1)

for _ in range(K):
  C, D = map(lambda x: int(x)-1, input().split())
  if uf.same(C, D):
    ans[C] -= 1
    ans[D] -= 1

print(*ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
BAD=[0 for i in range(n+1)]

E=[]
for inp in range(m):
    a,b=map(int,input().split())
    E.append((a,b))
    BAD[a]-=1
    BAD[b]-=1

B=[] 
for inp in range(k):
    a,b=map(int,input().split())
    B.append((a,b))
    
uf=[i for i in range(n+1)]
def uf_find(x,uf=uf):
    while uf[x]!=x:
        x=uf[x]
    return x       


res=[]

for ele in E:
    if uf_find(ele[0]) == uf_find(ele[1]):
        continue
    else:
        res.append((ele[0],ele[1])) #write result
        
        if uf_find(ele[0])>uf_find(ele[1]):
            uf[uf_find(ele[0])]=uf_find(ele[1])
        else:
            uf[uf_find(ele[1])]=uf_find(ele[0])

SCO=[0 for i in range(n+1)]
for i in range(1,n+1):
    SCO[uf_find(i)]+=1


for bl in B:
    if uf_find(bl[0])==uf_find(bl[1]):
        BAD[bl[0]]-=1
        BAD[bl[1]]-=1

ANS=[str(SCO[uf_find(i)] + BAD[i] -1) for i in range(1,n+1)]
print(" ".join(ANS))

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.p = [-1]*n
    # union by rank
    self.r = [1]*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 union(self, x, y):
    rx, ry = self.find(x), self.find(y)

    if rx != ry:
      if self.r[rx] > self.r[ry]:
        rx, ry = ry, rx
      if self.r[rx] == self.r[ry]:
        self.r[ry] += 1
      self.p[ry] += self.p[rx]
      self.p[rx] = ry

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

  def count_member(self, x):
    return -self.p[self.find(x)]
  
n,m,k=map(int,input().split())
uf=UnionFind(n)
ab,cd=[],[]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  uf.union(a,b)
  ab.append((a,b))
for i in range(k):
  c,d=map(int,input().split())
  c-=1
  d-=1
  cd.append((c,d))
cnt=[]
for i in range(n):
  t=uf.count_member(i)-1
  cnt.append(t)
for a,b in ab:
  if uf.same(a,b):
    cnt[a]-=1
    cnt[b]-=1
for c,d in cd:
  if uf.same(c,d):
    cnt[c]-=1
    cnt[d]-=1
print(*cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

Friend = [[] for _ in range(N)]
Block  = [[] for _ in range(N)]

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

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

UF = UnionFind(N)

for i in range(N):
    for friend in Friend[i]:
        UF.union(i,friend)

li = [0]*N
for i in range(N):
    li[i] += (UF.size[UF.find(i)]-1-len(Friend[i]))


for i in range(N):
    for block in Block[i]:
        if UF.same_check(block,i):
            li[i]-=1
         
print(*li)

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


class UnionFind:
    def __init__(self, n):
        self._parent = [i for i in range(n)]
        self._rank = [0 for _ in range(n)]
        self._group_size = [1 for _ in range(n)]
        self.num_of_groups = n

    def find(self, x):
        if self._parent[x] == x:
            return x
        px = self._parent[x]
        root = self.find(px)
        self._parent[x] = root
        return root

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self._rank[px] < self._rank[py]:
            self._parent[px] = py
            self._group_size[py] += self._group_size[px]
        else:
            self._parent[py] = px
            self._group_size[px] += self._group_size[py]
        if self._rank[px] == self._rank[py]:
            self._rank[py] += 1
        self.num_of_groups -= 1

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

    def group_size(self, x):
        px = self.find(x)
        return self._group_size[px]


def main():
    N, M, K = LI()
    AB = [LI1() for _ in range(M)]
    CD = [LI1() for _ in range(K)]

    uf = UnionFind(N)

    friend = [[] for _ in range(N)]
    block = [[] for _ in range(N)]

    for (a, b) in AB:
        friend[a].append(b)
        friend[b].append(a)
        uf.union(a, b)
    for (c, d) in CD:
        block[c].append(d)
        block[d].append(c)

    for i in range(N):
        gs = uf.group_size(i)
        bc = 0
        for bi in block[i]:
            bc += int(uf.is_same(i, bi))
        # print(i, gs, fc, bc)
        print(gs - len(friend[i]) - bc - 1, end=" ")


main()

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self._group_size = [1 for _ in range(n)]
        self.num_of_groups = n

    def find(self, x):
        if self.parent[x] == x:
            return x
        px = self.parent[x]
        root = self.find(px)
        self.parent[x] = root
        return root

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self._group_size[py] += self._group_size[px]
        else:
            self.parent[py] = px
            self._group_size[px] += self._group_size[py]
        if self.rank[px] == self.rank[py]:
            self.rank[py] += 1
        self.num_of_groups -= 1

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

    def group_size(self, x):
        px = self.find(x)
        return self._group_size[px]


def main():
    N, M, K = LI()
    AB = [LI1() for _ in range(M)]
    CD = [LI1() for _ in range(K)]

    uf = UnionFind(N)

    friend = [[] for _ in range(N)]
    block = [[] for _ in range(N)]

    for (a, b) in AB:
        friend[a].append(b)
        friend[b].append(a)
        uf.union(a, b)
    for (c, d) in CD:
        block[c].append(d)
        block[d].append(c)

    for i in range(N):
        gs = uf.group_size(i)
        fc, bc = 0, 0
        for fi in friend[i]:
            fc += int(uf.is_same(i, fi))
        for bi in block[i]:
            bc += int(uf.is_same(i, bi))
        # print(i, gs, fc, bc)
        print(gs - fc - bc - 1, end=" ")


main()

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.ps = [-1] * (n + 1)
 
    def find(self, x):
        if self.ps[x] < 0:
            return x
        else:
            self.ps[x] = self.find(self.ps[x])
            return self.ps[x]
 
    def 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]

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)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(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
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    def union(self, x, y):
        x,y = self.find(x), 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())

n,m,k = imap()
uf = unionfind(n)
f,ng,anss = iarr(n),iarr(n),iarr(n)

for i in range(m):
    a,b = imap()
    a,b = a-1,b-1
    f[a] += 1
    f[b] += 1
    uf.union(a,b)

for i in range(n):
    anss[i] = uf.size(i) - f[i] - 1

for i in range(k):
    c,d = imap()
    c,d = c-1,d-1
    if uf.same(c,d):
        anss[c] -= 1
        anss[d] -= 1

print(*anss)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。ノード番号は１から開始なのでn+1個。
        # par[x]<0の時そのノードは根で、par[x]の絶対値はグループのサイズ
        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]

    # xの属するグループとyの属するグループを併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

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

    # xが属するグループのサイズを返す
    def size(self, x):
        x = self.find(x)
        return -self.parents[x]

n, m, k = map(int, input().split())
friend = [list(map(int, input().split())) for _ in range(m)]
block = [list(map(int, input().split())) for _ in range(k)]

already = [0]*n
uf = UnionFind(n)

for a, b in friend:
    uf.union(a, b)
    already[a-1] += 1
    already[b-1] += 1

ans = [uf.size(x) - already[x-1] - 1 for x in range(1, n+1)]

for a, b in block:
    if uf.same(a, b):
        ans[a-1] -= 1
        ans[b-1] -= 1

print(*ans)

Submission status: Accepted

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

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

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

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

ans = [0 for i in range(n)]

def dfs(s):
  if vis[s] == False:
    vis[s] = True
    r[cnt].add(s)
    for i in ab[s]:
      dfs(i)

vis = [False for i in range(n)]
r = []
cnt = 0
for i in range(n):
  if vis[i] == False:
    r.append(set())
    dfs(i)
    cnt += 1

ans = [0 for i in range(n)]
for i in r:
  l = len(i)
  for j in i:
    ans[j] = l - len(ab[j]) - len(i&block[j]) - 1

print (*ans)

Submission status: Accepted

Solution code:
from queue import deque

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

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

checked = [False] * n
groups = []
for i in range(n):
    if checked[i]:
        continue
    checked[i] = True

    que = deque([i])
    group = [i]
    while que:
        now = que.popleft()
        friends_now = friends[now]
        for friend in friends_now:
            if checked[friend] == False:
                checked[friend] = True
                group.append(friend)
                que.append(friend)
    groups.append(group)

# print(groups)

D = dict()
for i in range(len(groups)):
    for j in groups[i]:
        D[j] = i

# print(D)

block = [0] * n
for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if D[c] == D[d]:
        block[c] += 1
        block[d] += 1

for i in range(n):
    group_i = D[i]
    print(len(groups[group_i]) - block[i] - len(friends[i]) - 1)

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
import copy

def dfs(now, group, groups, edges):
    if groups[now] != -1:
        return 0
    groups[now] = group
    cnt = 1
    for to in edges[now]:
        cnt += dfs(to, group, groups, edges)
    return cnt

def main():
    n, m, k = map(int, input().split())
    edges = [list() for i in range(n)]
    ngs = [list() for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        edges[a].append(b)
        edges[b].append(a)
    for i in range(k):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        ngs[c].append(d)
        ngs[d].append(c)


    cnt = 0
    groups = [-1 for i in range(n)]
    nodes_cnt = list()

    ans = [0 for i in range(n)]
    
    for i in range(n):
        if groups[i] == -1:
            nodes_cnt.append(dfs(i, cnt, groups, edges))
            cnt += 1
        ans[i] = nodes_cnt[groups[i]] - len(edges[i]) - 1
        for ng in ngs[i]:
            if groups[i] == groups[ng]:
                ans[i] -= 1

    print(*ans, sep=" ")

if __name__ == '__main__':
    sys.setrecursionlimit(1000000)
    sys.exit(main())

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

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

N,M,K = map(int,input().split())
u = UnionFind(N)
blocks = [0]*N
f_count = [0]*N
for i in range(M):
    a,b = I()
    f_count[a-1] += 1
    f_count[b-1] += 1
    u.unite(a-1,b-1)
for i in range(K):
    c,d = I()
    if u.root_same(c-1,d-1):
        blocks[c-1] += 1
        blocks[d-1] += 1
for i in range(N):
    print(u.count(i)-f_count[i]-blocks[i]-1)