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:
from itertools import chain


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)]
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    g = [-1] * (n + 1)
    s = 0
    while s < n:
        s += 1
        if g[s] >= 0:
            continue
        t, tt = set([s]), set(fr[s])
        while tt and t != tt:
            t, tt = t.union(tt), tt.union(set(chain.from_iterable(
                fr[i] for i in tt.difference(t))))
        for _t in t:
            g[_t] = len(t - set([_t]) - set(fr[_t]) - set(br[_t]))
    return " ".join(map(str, g[1:]))


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

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain


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)]
    for a, b in zip(*[iter(ab)] * 2):
        fr[a].append(b)
        fr[b].append(a)
    for c, d in zip(*[iter(cd)] * 2):
        br[c].append(d)
        br[d].append(c)

    g = [-1] * (n + 1)
    s = 0
    while s < n:
        s += 1
        if g[s] >= 0:
            continue
        t, tt = set([s]), set(fr[s])
        while tt and t != tt:
            t = t.union(tt)
            tt = tt.union(set(chain.from_iterable(fr[i] for i in tt)))
        for _t in t:
            g[_t] = len(t - set([_t]) - set(fr[_t]) - set(br[_t]))
    return " ".join(map(str, g[1:]))


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

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n

def unite(x, y):
  global clusterI
  CX = clusterI[x]
  CY = clusterI[y]
  if CX != CY:
    if CX < CY:
      CX, CY = CY, CX
    clusterN[CX] += clusterN[CY]
    clusterI = [CX if clusterI[i] == CY else clusterI[i] for i in range(n)]

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 clusterI[a-1] == clusterI[b-1]:
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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)]
F = [[]*N for i in range(N)]

def union(xx):
  f = [1<<N]*N
  for a,b in xx:
    a -= 1
    b -= 1
    f[a] = f[a] | 1<<(N-b-1)
    f[b] = f[b] | 1<<(N-a-1)
  return f

f = union(ab)
b = union(cd)
  
def add_link(ANS):
  for p,x in enumerate(ANS):
    res = 1<<N
    for i,xi in enumerate(str(bin(x)[3:])):
      if xi == '1':
        res = res | ANS[i]
    ANS[p] = res
  return ANS

ANS = f.copy()
for _ in range(N):
  ANS = add_link(ANS)

fb = [0]*N
ans = []
for p in range(N):
  fb[p] =  f[p] | b[p]
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans += [bin(ANS[p])[3:].count('1')]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N,M,K = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(M)]
cd = [list(map(int,input().split())) for i in range(K)]
F = [[]*N for i in range(N)]

def union(xx):
  f = [1<<N]*N
  for a,b in xx:
    a -= 1
    b -= 1
    f[a] = f[a] | 1<<(N-b-1)
    f[b] = f[b] | 1<<(N-a-1)
  return f

f = union(ab)
b = union(cd)

def conv(p):
  res = 1<<N
  for i,x in enumerate(p):
    res = res | x<<(N-i-1)
  return res
  
def add_link(ANS):
  for p,x in enumerate(ANS):
    res = 1<<N
    for i,xi in enumerate(str(bin(x)[3:])):
      if xi == '1':
        res = res | ANS[i]
    ANS[p] = res
  return ANS

ANS = f.copy()
pre = []
while ANS != pre:
  pre = ANS.copy()
  ANS = add_link(ANS)

pre = ANS.copy()
fb = [0]*N
ans_p = [0]*N
ans = ''
for p in range(N):
  fb[p] =  f[p] | b[p]
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans_p[p] = sum([int(x) for x in bin(ANS[p])[3:]])
  ans += str(ans_p[p]) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, k = map(int, input().split())
    friends = [[0 for _ in range(n+1)] for _ in range(n+1)]
    block = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for _ in range(m):
        a, b = map(int, input().split())
        friends[a][b] = 1
        friends[b][a] = 1
    for _ in range(k):
        a, b = map(int, input().split())
        block[a][b] = 1
        block[b][a] = 1
    # print(friends[1:], block[1:])

    cand_friends = [[0 for _ in range(n+1)] for _ in range(n+1)]
    def search_cand(now_node, i):
        for next_node, num in enumerate(friends[now_node]):
            if num == 1 and cand_friends[i][next_node] == 0:
                cand_friends[i][next_node] = 1
                search_cand(next_node, i)

    for i in range(1, n+1):
        now_node = i
        search_cand(now_node, i)
        cand_friends[i][i] = 0
        cand_num = sum(cand_friends[i]) - sum(friends[i])
        for b, num in enumerate(block[i]):
            if num==1 and cand_friends[i][b]==1:
                cand_num -= 1
        print(cand_num, end=' ')
    print("")
    # print(cand_friends[1:])

if __name__=='__main__':
    # import time
    # start = time.time()
    main()
    # print(f"{time.time()-start}[s]")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,k = [int(x) for x in input().split()]
l = [[] for i in range(n+1)]
p = []
q = []
d2 = deque()
for i in range(m):
    p.append(list(map(int, input().split())))
for i in range(k):
    q.append(list(map(int, input().split())))
for pi in p:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
#ここまでで、グラフが隣接リスト表記で表される
dist =[[-1] * (n+1) for i in range(n+1)]
for z in range(1,n+1):
  d = deque()
  dist[z][z] = 0
  d.append(z)
  while True:
    v = d.popleft()
    for i in l[v]:
      if dist[z][i] != -1:
        continue
      dist[z][i] = dist[z][v] + 1
      d.append(i)
    if not d:
      break
for qi in q:  
    dist[qi[0]][qi[1]] = -1
    dist[qi[1]][qi[0]] = -1
for i in range(1,n+1):
  print(1+n-dist[i].count(0)-dist[i].count(1)-dist[i].count(-1),end=" ")

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 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()
for _ in range(m):
  a,b=map(int,input().split())
  uf.unite(a-1,b-1)
  s.add((a-1,b-1))
  s.add((b-1,a-1))
for _ in range(k):
  c,d=map(int,input().split())
  s.add((c-1,d-1))
  s.add((d-1,c-1))
ans=[]
for i in range(n):
  res=uf.size(i)
  for j in uf.members(i):
    if i==j:
      continue
    if (i,j) in s:
      res-=1
  ans.append(res-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n

def unite(x, y):
  CX = clusterI[x]
  CY = clusterI[y]
  if CX != CY:
    if CX < CY:
      CX, CY = CY, CX
    clusterN[CX] += clusterN[CY]
    for i in range(n):
      if clusterI[i] == CY:
        clusterI[i] = 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 clusterI[a-1] == clusterI[b-1]:
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)

Submission status: Time Limit Exceeded

Solution code:

N,M,K = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(M)]
cd = [list(map(int,input().split())) for i in range(K)]
F = [[]*N for i in range(N)]

def union(xx):
  f = [1<<N]*N
  for a,b in xx:
    a -= 1
    b -= 1
    f[a] = f[a] | 1<<(N-b-1)
    f[b] = f[b] | 1<<(N-a-1)
  return f

f = union(ab)
b = union(cd)

def conv(p):
  res = 1<<N
  for i,x in enumerate(p):
    res = res | x<<(N-i-1)
  return res
  
def add_link(ANS):
  for p,x in enumerate(ANS):
    res = 1<<N
    for i,xi in enumerate(str(bin(x)[3:])):
      if xi == '1':
        res = res | ANS[i]
    ANS[p] = res
  return ANS

ANS = f.copy()
pre = []
while ANS != pre:
  pre = ANS.copy()
  ANS = add_link(ANS)

pre = ANS.copy()
fb = [0]*N
ans_p = [0]*N
ans = ''
for p in range(N):
  fb[p] =  f[p] | b[p]
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans_p[p] = sum([int(x) for x in bin(ANS[p])[3:]])
  ans += str(ans_p[p]) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:

N,M,K = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(M)]
cd = [list(map(int,input().split())) for i in range(K)]
F = [[]*N for i in range(N)]
f = [1<<N]*N
for a,b in ab:
  a -= 1
  b -= 1
  f[a] = f[a] | 1<<(N-b-1)
  f[b] = f[b] | 1<<(N-a-1)
  F[a] = F[a] + [b]
  F[b] = F[b] + [a]
b = [1<<N]*N
for c,d in cd:
  c -= 1
  d -= 1
  b[c] = b[c] | 1<<(N-d-1)
  b[d] = b[d] | 1<<(N-c-1)

def conv(p):
  res = 1<<N
  for i,x in enumerate(p):
    res = res | x<<(N-i-1)
  return res
  
def add_link(ANS):
  for p,x in enumerate(F):
    res = 1<<N
    for i in x:
      res = res | ANS[int(i)]
    ANS[p] = res
  return ANS

ANS = f.copy()
pre = []

while ANS != pre:
  pre = ANS.copy()
  ANS = add_link(ANS)

pre = ANS.copy()
fb = [0]*N
ans_p = [0]*N
ans = ''
for p in range(N):
  fb[p] =  f[p] | b[p]
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans_p[p] = sum([int(x) for x in bin(ANS[p])[3:]])
  ans += str(ans_p[p]) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
friend = [set() for i in range(n)]
block = [set() for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    friend[a].add(b)
    friend[b].add(a)
for _ in range(k):
    c, d = map(lambda x: int(x) - 1, input().split())
    block[c].add(d)
    block[d].add(c)

group = [set() for _ in range(n)]
group_id = [n+1] * n
id_ = 0
no_visit = set(range(n))
while len(no_visit) > 0:
    connect = set()
    connect.add(no_visit.pop())
    while len(connect) > 0:
        tmp = connect.pop()
        group_id[tmp] = id_
        new = friend[tmp] & no_visit
        connect = connect | new
        for i in new:
            no_visit.discard(i)
    id_ += 1

for i in range(n):
    group[group_id[i]].add(i)

ans = [0] * n
for i in range(n):
    ans[i] = len(group[group_id[i]] - friend[i] - block[i]) - 1
print(*ans)

Submission status: Time Limit Exceeded

Solution code:

N,M,K = list(map(int,input().split()))
F = [[]*N for i in range(N)]
f = [1<<N]*N
b = [1<<N]*N
for i in range(M):
  R = list(map(int,input().split()))
  f[R[0]-1] = f[R[0]-1] | 1<<(N-(R[1]-1)-1)
  f[R[1]-1] = f[R[1]-1] | 1<<(N-(R[0]-1)-1)
  F[R[0]-1] = F[R[0]-1] + [R[1]-1]
  F[R[1]-1] = F[R[1]-1] + [R[0]-1]

for i in range(K):
  R = list(map(int,input().split()))
  b[R[0]-1] = b[R[0]-1] | 1<<(N-(R[1]-1)-1)
  b[R[1]-1] = b[R[1]-1] | 1<<(N-(R[0]-1)-1)

def conv(p):
  res = 1<<N
  for i,x in enumerate(p):
    res = res | x<<(N-i-1)
  return res
  
def add_link(ANS):
  for p,x in enumerate(F):
    res = 1<<N
    for i in x:
      res = res | ANS[int(i)]
    ANS[p] = res
  return ANS

ANS = f.copy()
pre = []
while ANS != pre:
  pre = ANS.copy()
  ANS = add_link(ANS)

pre = ANS.copy()
fb = [0]*N
ans_p = [0]*N
ans = ''
for p in range(N):
  fb[p] =  f[p] | b[p]
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans_p[p] = sum([int(x) for x in bin(ANS[p])[3:]])
  ans += str(ans_p[p]) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:

N,M,K = list(map(int,input().split()))
F = [[]*N for i in range(N)]
f = [1<<N]*N
b = [1<<N]*N
for i in range(M):
  R = list(map(int,input().split()))
  f[R[0]-1] |= 1<<(N-(R[1]-1)-1)
  f[R[1]-1] |= 1<<(N-(R[0]-1)-1)
  F[R[0]-1] += [R[1]-1]
  F[R[1]-1] += [R[0]-1]

for i in range(K):
  R = list(map(int,input().split()))
  b[R[0]-1] |= 1<<(N-(R[1]-1)-1)
  b[R[1]-1] |= 1<<(N-(R[0]-1)-1)

def conv(p):
  res = 1<<N
  for i,x in enumerate(p):
    res |= x<<(N-i-1)
  return res
  
def add_link(ANS):
  for p,x in enumerate(F):
    res = 1<<N
    for i in x:
      res |= ANS[int(i)]
    ANS[p] = res
  return ANS

ANS = f.copy()
pre = []
while ANS != pre:
  pre = ANS.copy()
  ANS = add_link(ANS)

pre = ANS.copy()
fb = [0]*N
ans_p = [0]*N
ans = ''
for p in range(N):
  fb[p] =  f[p] | b[p]
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans_p[p] = sum([int(x) for x in bin(ANS[p])[3:]])
  ans += str(ans_p[p]) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int, input().split())
par=list(range(N))
nums=[0 for _ in range(N)]
rank=[0 for _ in range(N)]
#実装
def find(x):
    if par[x]==x:
        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
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1
def same(x,y):
    return find(x)==find(y)

checked=[]

for _ in range(M):
  a1,a2=map(int, input().split())
  a1-=1
  a2-=1
  if (min(a1,a2),max(a1,a2)) not in checked:
    checked.append((min(a1,a2),max(a1,a2)))
    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) and (min(a1,a2),max(a1,a2)) not in checked:
    nums[a1]-=1
    nums[a2]-=1
  if (min(a1,a2),max(a1,a2)) not in checked:
    checked.append((min(a1,a2),max(a1,a2)))
for i in range(N):
    par[i]=find(i)

for i in range(N):
    nums[i]=nums[i]+par.count(par[i])-1
print(" ".join(list(map(str,nums))))

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int, input().split())
par=list(range(N))
rank=[0 for _ in range(N)]
#実装
def find(x):
    if par[x]==x:
        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
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1
def same(x,y):
    return find(x)==find(y)

eandb=[(i,i)for i in range(N)]
for _ in range(M):
  a1,a2=map(int, input().split())
  a1-=1
  a2-=1
  eandb.append((a1,a2))
  eandb.append((a2,a1))
  unite(a1,a2)
for _ in range(K):
  a1,a2=map(int, input().split())
  a1-=1
  a2-=1
  eandb.append((a1,a2))
  eandb.append((a2,a1))
ans=[]
for i in range(N):
  ans_i=len([ bb for bb in range(N) if same(bb,i) and (bb,i) not in eandb])
  ans.append(str(ans_i))
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_d

class UnionFind:
    def __init__(self, parents):
        self.parents = parents

    def find(self, a):
        pa = self.parents[a]
        if pa == a:
            return pa
        self.parents[a] = self.find(pa)
        return self.parents[a]

    def unite(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        if pa == pb:
            return

        self.parents[pa] = pb

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


N, M, K = map(int, input().split())
union = UnionFind([i for i in range(N)])

m = [[i != j for i in range(N)] for j in range(N)]

for _ in range(M):
    A, B = map(int, input().split())
    m[A - 1][B - 1] = 0
    m[B - 1][A - 1] = 0
    union.unite(A - 1, B - 1)

for _ in range(K):
    A, B = map(int, input().split())
    m[A - 1][B - 1] = 0
    m[B - 1][A - 1] = 0

for j, row in enumerate(m):
    ans = 0
    for i, e in enumerate(row):
        if e == 0:
            continue
        ans += union.same(i, j)

    print(ans, end=' ')

Submission status: Time Limit Exceeded

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

groups = [None] * N
group_num = -1

for start in range(N):
    if groups[start] is not None:
        continue
    group_num += 1
    stack = []
    stack.append(start)
    groups[start] = group_num 
    while stack:
        person = stack.pop()
        for new_person in friend[person]:
            if groups[new_person] is None:
                stack.append(new_person)
                groups[new_person] = group_num

groups_dict = [set() for _ in range(group_num+1)]
for i, group in enumerate(groups):
    groups_dict[group].add(i)

answer = [0] * N
for i in range(N):
    nominees = groups_dict[groups[i]].copy()
    nominees -= friend[i]
    nominees -= blocked[i]
    answer[i] = len(nominees) - 1

print(' '.join([str(num) for num in answer]))

Submission status: Time Limit Exceeded

Solution code:

N,M,K = list(map(int,input().split()))
f = [[0]*N for i in range(N)]
b = [[0]*N for i in range(N)]
for i in range(M):
  R = list(map(int,input().split()))
  f[R[0]-1][R[1]-1] = 1
  f[R[1]-1][R[0]-1] = 1

for i in range(K):
  R = list(map(int,input().split()))
  b[R[0]-1][R[1]-1] = 1
  b[R[1]-1][R[0]-1] = 1

def conv(p):
  res = 1<<N
  for i,x in enumerate(p):
    res |= x<<(N-i-1)
  return res
  
def add_link(ANS):
  for p in range(N):
    res = 1<<N
    for i,x in enumerate(bin(ANS[p])[3:]):
      if x == '1':
        res |= ANS[i]
    ANS[p] = res
  return ANS

ANS = [0]*N
for i,p in enumerate(f):
  ANS[i] = conv(p)

pre = []
while ANS != pre:
  pre = ANS.copy()
  ANS = add_link(ANS)


fb = [0]*N
ans_p = [0]*N
ans = ''
for p in range(N):
  fb[p] = conv(f[p]) | conv(b[p])
  ANS[p] = ANS[p] | fb[p]
  ANS[p] = ANS[p] ^ fb[p]
  ans_p[p] = sum([int(x) for x in bin(ANS[p])[3:]])
  ans += str(ans_p[p]) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

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_tree1 = UnionFind(N)
uf_tree2 = 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_tree1.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;
    uf_tree2.unite(c, d)
    blocks[c].append(d)
    blocks[d].append(c)

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

Submission status: Time Limit Exceeded

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
  block_list[i] |={j}
  block_list[j] |={i}

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

Submission status: Time Limit Exceeded

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 = list(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 = list(map(int,input().split()))
  i-=1
  j-=1
  block_list[i] |={j}
  block_list[j] |={i}

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

Submission status: Time Limit Exceeded

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.d = None
    
  def union(self,i,j):
    if not self.connected(i,j):
      root = self.root(i)
      for node in self.path(i):
        self.l[node] = root
      for node in self.path(j):
        self.l[node] = root
  
  def path(self,i):
    result = [i]
    while self.l[i] != i:
      i = self.l[i]
      result.append(self.l[i])
    return result
  
  def root(self,i):
    while self.l[i] != i:
      i = self.l[i]
    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 = list(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 = list(map(int,input().split()))
  i-=1
  j-=1
  block_list[i] |={j}
  block_list[j] |={i}
from collections import Counter 

c = Counter(uf.l)
whole = {i for i in range(N)}
for i in range(N):
  c_set = uf.connected_set(i)
  print(len(c_set - direct_connected[i] - block_list[i]-{i}),end=" ")

Submission status: Time Limit Exceeded

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):
      root = self.root(i)
      merged_size = self.size[i] + self.size[j] 
      self.size[i] = merged_size
      self.size[j] = merged_size
      for node in self.path(i):
        self.l[node] = root
      for node in self.path(j):
        self.l[node] = root
  
  def path(self,i):
    result = [i]
    while self.l[i] != i:
      i = self.l[i]
      result.append(self.l[i])
    return result
  
  def root(self,i):
    while self.l[i] != i:
      i = self.l[i]
    return i
    
  def connected(self,i,j):
    if self.root(i) == self.root(j):
      return True
    else:
      return False
    
  def size(self,i):
    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 = list(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 = list(map(int,input().split()))
  i-=1
  j-=1
  block_list[i] |={j}
  block_list[j] |={i}
from collections import Counter 

c = Counter(uf.l)
whole = {i for i in range(N)}
for i in range(N):
  c_set = uf.connected_set(i)
  print(len(c_set - direct_connected[i] - block_list[i]-{i}),end=" ")