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:
import sys
sys.setrecursionlimit(10 ** 9)

class Union_Find:
    def __init__(self, n = 0):
        self.d = [-1] * n
    
    def find(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]
    
    def unite(self, x: int, y: int) -> bool:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        return -1 * self.d[self.find(x)]


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

friends = [0] * n
blocks = [[] for _ in range(n)]

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

for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    blocks[c].append(d)
    blocks[d].append(c)

ans = []
for i in range(n):
    candidates = uf.size(i) - 1 - friends[i]
    for u in blocks[i]:
        if uf.same(i, u):
            candidates -= 1
    ans.append(candidates)

print(*ans)

Submission status: Accepted

Solution code:
def init(n):
    par = list(range(n))
    size = [1] * n
    return par, size

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

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if size[x] < size[y]:
        par[x] = y
        size[y] += size[x]
    else:
        par[y] = x
        size[x] += size[y]


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

par, size = init(N+1)
non_candidates = [1] * (N+1)
for i in range(M):
    a, b = map(int, input().split())
    unite(a, b)
    non_candidates[a] += 1
    non_candidates[b] += 1
    

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

for i in range(1, N+1):
    print(size[root(i)] - non_candidates[i], end=" ")
    # print(i, size[root(i)], non_candidates[i])

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
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]

N,M,K = inputlist()
uf = UnionFind(N+1)
graph = [[] for _ in range(N+1)]
for i in range(M):
    a,b = inputlist()
    uf.union(a,b)
    graph[a].append(b)
    graph[b].append(a)
brogra = [[] for _ in range(N+1)]
li = [0]*N
for i in range(K):
    c,d = inputlist()
    if uf.same(c,d):
        brogra[c].append(d)
        brogra[d].append(c)
for i in range(1,N+1):
    li[i-1] = uf.size(i) - len(graph[i]) - len(brogra[i]) -1
print(*li)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    r = [1] * (n + 1)
    uf = UnionFind(n)
    for a, b in zip(*[iter(abcd[:2 * m])] * 2):
        r[a] += 1
        r[b] += 1
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        uf.t[i] = i if v < 0 else v
    mp = {k: set([]) for k in set(uf.t[1:])}
    for i, v in enumerate(uf.t[1:], start=1):
        mp[v].add(i)
    for c, d in zip(*[iter(abcd[2 * m:])] * 2):
        r[c] += 1 if d in mp[uf.t[c]] else 0
        r[d] += 1 if c in mp[uf.t[d]] else 0
    mp = {k: len(v) for k, v in mp.items()}
    return " ".join([str(mp[uf.t[i]] - r[i]) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    r = [0] * (n + 1)
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        r[a] += 1
        r[b] += 1
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: [] for k in set(uf.t[1:])}
    for i, v in enumerate(uf.t[1:], start=1):
        mp[v].append(i)
    mp = {k: set(v) for k, v in mp.items()}
    for c, d in zip(*[iter(cd)] * 2):
        r[c] += 1 if d in mp[uf.t[c]] else 0
        r[d] += 1 if c in mp[uf.t[d]] else 0
    mp = {k: len(v) for k, v in mp.items()}
    return " ".join([str(mp[uf.t[i]] - 1 - r[i]) for i in range(1, n + 1)])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.t = [-1] * (n + 1)

    def flatten(self):
        for i, _ in enumerate(self.t):
            self.find_root(i)

    def union(self, a, b):
        ra = self.find_root(a)
        rb = self.find_root(b)
        if ra != rb:
            self.t[max(ra, rb)] = min(ra, rb)

    def find_root(self, x):
        t = []
        while self.t[x] > 0:
            t.append(x)
            x = self.t[x]
        for _t in t:
            self.t[_t] = x
        return x


def solve(string):
    n, m, k, *abcd = map(int, string.split())
    ab, cd = abcd[:2 * m], abcd[2 * m:]
    fr, br = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]
    uf = UnionFind(n)
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
        uf.union(a, b)
    uf.flatten()
    for i, v in enumerate(uf.t):
        if v < 0:
            uf.t[i] = i
    mp = {k: i for i, k in enumerate(set(uf.t[1:]))}
    g = [[] for _ in enumerate(mp.keys())]
    for i in range(n + 1):
        if uf.t[i] > 0:
            g[mp[uf.t[i]]].append(i)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    *fr, = map(len, fr)
    *g, = map(set, g)
    *gn, = map(len, g)
    return " ".join([
        str(gn[mp[uf.t[i]]] - 1 - fr[i] - sum(j in g[mp[uf.t[i]]]
                                              for j in br[i]))
        for i in range(1, n + 1)
    ])


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def find(x):
  if clusterI[x] != x:
    minI = find(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = find(x)
  CY = find(y)
  if CX != CY:
    if CX > CY:
      CX, CY = CY, CX
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    

for _ in range(m):
  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if find(a-1) == find(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[find(i)] - 1 for i in range(n)]
print(*out)

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def generateC(x):
  if clusterI[x] != x:
    minI = generateC(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = generateC(x)
  CY = generateC(y)
  if CX != CY:
    if CX > CY:
      CX, CY = CY, CX
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    generateC(y)
    

for _ in range(m):
  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if generateC(a-1) == generateC(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[generateC(i)] - 1 for i in range(n)]
print(*out)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from collections import Counter
G = []
H = []
color = []


def dfs(G, i, fr, c):
    global color
    color[i] = c
    # print('lp')
    for node in G[i]:
        if color[node] == -1:
            dfs(G, node, i, c)


def main():
    global G, H, color
    n, m, k = list(map(int, input().strip().split()))
    G = [[] for _ in range(n)]
    H = [[] for _ in range(n)]
    color = [-1] * n
    for i in range(m):
        a, b = list(map(lambda x: x-1, map(int, input().strip().split())))
        G[a].append(b)
        G[b].append(a)
    for i in range(k):
        a, b = list(map(lambda x: x-1, map(int, input().strip().split())))
        H[a].append(b)
        H[b].append(a)
    c = 0
    # print(G)
    for i in range(n):
        # print('before dfs')
        if color[i] == -1:
            dfs(G, i, -1, c)
            c += 1
        # print('af dfs')
    counter = dict(Counter(color))
    # print(counter)
    # print(color)
    # print(H)
    for i in range(n):
        block = 0
        for b in H[i]:
            if color[i] == color[b]:
                block += 1
        # print('block, ', block)
        print(counter[color[i]] - 1 - len(G[i]) - block)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.d = [-1 for _ in range(n)]
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]

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

N, M, K = map(int, input().split())
dame = [[] for _ in range(N)]
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    dame[a].append(b)
    dame[b].append(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].append(d)
    dame[d].append(c)

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

print()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
uf=UnionFind(n)
s=set()
cnt=[0]*n
for _ in range(m):
  a,b=map(int,input().split())
  uf.unite(a-1,b-1)
  cnt[a-1]+=1
  cnt[b-1]+=1
for _ in range(k):
  c,d=map(int,input().split())
  if uf.same(c-1,d-1):
    cnt[c-1]+=1
    cnt[d-1]+=1
ans=[]
for i in range(n):
  ans.append(uf.size(i)-cnt[i]-1)
print(*ans)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
#Union Find
N,M,K = inputlist()
graph = [[] for _ in range(N)]
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*(N)
for i in range(M):
    A,B = inputlist()
    graph[A-1].append(B-1)
    graph[B-1].append(A-1)
    unite(A-1,B-1)
bgraph = [[] for _ in range(N)]
for i in range(K):
    C,D = inputlist()
    if same(C-1,D-1):
        bgraph[C-1].append(D-1)
        bgraph[D-1].append(C-1)
li = [0]*N
for i in range(N):
    k = size(i)
    n = len(graph[i])
    m = len(bgraph[i])
    li[i] = k-n-m-1
print(*li)

Submission status: Accepted

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
class uf:
    def __init__(self,n):
        self.n=n
        self.l=[-1]*n
    def ro(self,n):
        if self.l[n]<0:
            return n
        r=self.ro(self.l[n])
        self.l[n]=r
        return r
    def me(self,a,b):
        ra=self.ro(a)
        rb=self.ro(b)
        if self.l[ra]>self.l[rb]:
            ra,rb=rb,ra
        if ra!=rb:
            self.l[ra]+=self.l[rb]
            self.l[rb]=ra
    def size(self,n):
        return -self.l[self.ro(n)]
    def sa(self,a,b):
        return self.ro(a)==self.ro(b)
N,M,K=map(int,input().split())
u=uf(N)
l=[-1]*N
for i in range(M):
    A,B=map(lambda x: int(x)-1,input().split())
    u.me(A,B)
    l[A]-=1
    l[B]-=1
for i in range(N):
    l[i]+=u.size(i)
for i in range(K):
    C,D=map(lambda x: int(x)-1,input().split())
    if u.sa(C,D):
        l[C]-=1
        l[D]-=1
print(*l)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
class uf:
    def __init__(self,n):
        self.n=n
        self.l=[-1]*n
    def ro(self,n):
        if self.l[n]<0:
            return n
        r=self.ro(self.l[n])
        self.l[n]=r
        return r
    def me(self,a,b):
        ra=self.ro(a)
        rb=self.ro(b)
        if ra!=rb:
            self.l[ra]+=self.l[rb]
            self.l[rb]=ra
    def size(self,n):
        return -self.l[self.ro(n)]
    def sa(self,a,b):
        return self.ro(a)==self.ro(b)
N,M,K=map(int,input().split())
u=uf(N)
l=[-1]*N
for i in range(M):
    A,B=map(lambda x: int(x)-1,input().split())
    u.me(A,B)
    l[A]-=1
    l[B]-=1
for i in range(N):
    l[i]+=u.size(i)
for i in range(K):
    C,D=map(lambda x: int(x)-1,input().split())
    if u.sa(C,D):
        l[C]-=1
        l[D]-=1
print(*l)

Submission status: Accepted

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

n,m,k=map(int,input().split())
uf=UF(n)
F=[[]for _ in range(n)]
P=[0]*n
B=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    F[a-1].append(b-1)
    F[b-1].append(a-1)
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1
for i in range(n):
    P[i]=uf.size(i)-1+B[i]-len(F[i])
print(*P)

Submission status: Accepted

Solution code:
N,M,K=map(int, input().split())
par=[-1 for _ in range(N)]
nums=[-1 for _ in range(N)]
#実装
def find(x):
    if par[x]<0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

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

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


for _ in range(M):
    a1,a2=map(int, input().split())
    a1-=1
    a2-=1
    unite(a1,a2)
    nums[a1]-=1
    nums[a2]-=1

for _ in range(K):
    a1,a2=map(int, input().split())
    a1-=1
    a2-=1
    if same(a1,a2):
        nums[a1]-=1
        nums[a2]-=1


for i in range(N):
    nums[i]+=size(i)

print(" ".join(list(map(str,nums))))

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)

    
number_list = list(map(int, input().split()))
N = number_list[0]
M = number_list[1]
K = number_list[2]

M_list = [list(map(int, input().split())) for _ in range(M)]

K_list = [list(map(int, input().split())) for _ in range(K)]

uf = UnionFind(N)
for i in range(M):
    uf.union(M_list[i][0]-1,M_list[i][1]-1)

fbcnt = [0]*N

for k in range(M):
    fbcnt[M_list[k][0]-1] += 1
    fbcnt[M_list[k][1]-1] += 1
for j in range(K):
    if uf.same(K_list[j][0]-1,K_list[j][1]-1):
        fbcnt[K_list[j][0]-1] += 1
        fbcnt[K_list[j][1]-1] += 1

result = []
for l in range(N):
    result.append(uf.size(l)-fbcnt[l]-1)

result = [str(a) for a in result]
result = ' '.join(result)
print(result)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
def r(x):
  while p[x]>=0: x=p[x]
  return x
def u(x,y):
  x,y=r(x),r(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]; p[y]=x
n,m,k=f()
l,p=[0]*-~n,[-1]*-~n
for _ in range(m):
  a,b=f()
  u(a,b); l[a]-=1; l[b]-=1
for _ in range(k):
  c,d=f()
  if r(c)==r(d): l[c]-=1; l[d]-=1
for i in range(n+1): l[i]-=p[r(i)]+1
print(*l[1:])

Submission status: Accepted

Solution code:
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,m,k=f()
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]
l=[0]*n
for _ in range(m):
  a,b=f()
  unite(a-1,b-1)
  l[a-1]-=1
  l[b-1]-=1
for _ in range(k):
  c,d=f()
  if same(c-1,d-1):
    l[c-1]-=1
    l[d-1]-=1
for i in range(n):
  l[i]+=size(i)-1
print(*l)

Submission status: Accepted

Solution code:
import sys
f=lambda:tuple(map(int,sys.stdin.readline().split()))
n,m,k=f()
lta=[f() for _ in range(m)]
ltb=[f() for _ in range(k)]
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]
l=[0]*n
for a,b in lta:
  unite(a-1,b-1)
  l[a-1]-=1
  l[b-1]-=1
for c,d in ltb:
  if same(c-1,d-1):
    l[c-1]-=1
    l[d-1]-=1
for i in range(n):
  l[i]+=size(i)-1
print(*l)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1

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

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

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


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

uf_tree = UnionFind(N)

friends = [ [] for _ in range(N) ]
blocks = [ [] for _ in range(N) ]

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

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

for i in range(N):
    ans = uf_tree.size(i) - 1
    cand = set()
    for f in friends[i]:
        cand.add(f)
    for b in blocks[i]:
        if uf_tree.same(i, b):
            cand.add(b)
    ans -= len(cand)
    print(ans, end = "")
    print("\n" if i == N-1 else " ", end = "")

Submission status: Accepted

Solution code:
def find(x):
  if par[x] < 0:
    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 x>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)]

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

par = [-1]*n
FF = [0] * n
BB = [[] for i in range(n)]

for i in range(m):
  a, b = map(int, input().split())
  unite(a-1, b-1)
  FF[a-1] += 1
  FF[b-1] += 1
for i in range(k):
  a, b = map(int, input().split())
  BB[a-1].append(b-1)
  BB[b-1].append(a-1)
result = []

for i in range(n):
  ans = size(i) - FF[i] -1
  for j in BB[i]:
    if same(i, j):
      ans -= 1
  result.append(ans)
  
print(*result)

Submission status: Accepted

Solution code:
N,M,K = list(map(int,input().split()))
import sys
input = sys.stdin.readline
from collections import defaultdict
class UF():
  def __init__(self,n):
    self.n_node = n
    self.l = [i for i in range(n)]
    self.size = [1 for i in range(n)]
    self.d = None
  
  def union(self,i,j):
    if not self.connected(i,j):
      iroot,ipath = self.root(i,return_path=True)
      jroot,jpath = self.root(j,return_path=True)
      if len(jpath) < len(ipath):
        for node in ipath + jpath:
          self.l[node] = iroot
      else:
        for node in ipath + jpath:
          self.l[node] = jroot
        
  def root(self,i,return_path=False):
    path = [i]
    while self.l[i] != i:
      i = self.l[i]
      path.append(self.l[i])
    
    if return_path:
      return i,path
    else:
      return i
  
  def connected(self,i,j):
    if self.root(i) == self.root(j):
      return True
    else:
      return False
  
  def simplify(self):
    for node in range(self.n_node):
      root = self.root(self.l[node])
      if self.l[node] != root:
        self.l[node] = root
  
  def calc_connected(self):
    self.d = defaultdict(set)
    self.simplify()
    for idx,root in enumerate(self.l):
      self.d[root] |= {idx}
    
  def connected_set(self,i):
    if self.d is None:
      self.calc_connected()
    return self.d[self.root(i)]
      
uf = UF(N)
direct_connected = defaultdict(set)
for i in range(M):
  i,j = map(int,input().split())
  i-=1
  j-=1
  
  uf.union(i,j)
  direct_connected[i] |= {j}
  direct_connected[j] |= {i}

block_list = defaultdict(set)
for i in range(K):
  i,j = map(int,input().split())
  i-=1
  j-=1
  if uf.connected(i,j):
    block_list[i] |={j}
    block_list[j] |={i}

  
uf.calc_connected()
for i in range(N):
  print(len(uf.d[uf.l[i]]) - len(direct_connected[i]) - len(block_list[i])-1,end=" ")

Submission status: Accepted

Solution code:
import sys

def main():
    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)]

    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)
    ans = [0]*n
    cnt = [0]*n

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

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

    for c,d in cd:
        if uf.same(c-1, d-1):
            ans[c-1] -= 1
            ans[d-1] -= 1

    for i in range(n):
        print(ans[i] - cnt[i] - 1, end = ' ')

if __name__ == '__main__':
    main()