Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
fr=[input() for i in range(m)]
bl=[input() for i in range(k)]
relfr=[set() for i in range(n)]
relbl=[set() for i in range(n)]
for l in fr:
  a,b=map(int,l.split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for l in bl:
  a,b=map(int,l.split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
cand=[0]
searched=set()
gr=set()
all_gr={i for i in range(n)}
ans=['']*n
while all_gr!=searched:
  while len(cand)!=0:
    now=cand.pop()
    gr.add(now)
    for point in relfr[now]:
      if not point in gr and not point in cand:
        cand.append(point)
  for i in gr:
    ans[i]=str(len(gr)-len(relfr[i])-len(relbl[i]&gr)-1)
    searched.add(i)
  gr.clear()
  if all_gr!=searched:
    cand.append(list(all_gr-searched)[0])
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
fr=[input() for i in range(m)]
bl=[input() for i in range(k)]
relfr=[[] for i in range(n)]
relbl=[[] for i in range(n)]
for l in fr:
  a,b=map(int,l.split())
  relfr[a-1].append(b-1)
  relfr[b-1].append(a-1)
for l in bl:
  a,b=map(int,l.split())
  relbl[a-1].append(b-1)
  relbl[b-1].append(a-1)
cand=[0]
searched=set()
gr=[]
all_gr={i for i in range(n)}
ans=['']*n
while all_gr!=searched:
  while len(cand)!=0:
    now=cand.pop()
    gr.append(now)
    for point in relfr[now]:
      if not point in gr and not point in cand:
        cand.append(point)
  for i in gr:
    ans[i]=str(len(gr)-len(relfr[i])-len([0 for _ in relbl[i] if _ in gr])-1)
    searched.add(i)
  gr=[]
  if all_gr!=searched:
    cand.append(list(all_gr-searched)[0])
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
class union():
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.friends = [0 for i in range(n)]
        self.blocks = [[] for i in range(n)]
        self.counts = [1] * n
        self.block_counts = [0] * n
    def find(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.find(self.par[n])
    def block(self, a, b):
        self.blocks[a].append(b)
        self.blocks[b].append(a)
        if self.same(a, b):
            self.block_counts[a] += 1
            self.block_counts[b] += 1
    def unite(self, a, b):
        x = self.find(a)
        y = self.find(b)
        self.friends[a] += 1
        self.friends[b] += 1
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, a, b):
        return self.find(a) == self.find(b)
    def optimize(self):
        self.par = list(map(self.find, self.par))
        for i in range(self.n):
            self.counts[i] = self.par.count(i)    
def main():
    N, M, K = map(int, input().split())
    AB = [list(map(lambda x:int(x)-1, input().split())) for i in range(M)]
    CD = [list(map(lambda x:int(x)-1, input().split())) for i in range(K)]
    u = union(N)
    unite = u.unite
    block = u.block
    for a, b in AB:
        unite(a, b)
    for c, d in CD:
        block(c, d)
    u.optimize()
    counts = u.counts
    par = u.par
    friends = u.friends
    block_counts = u.block_counts
    result = [str(counts[par[i]] - friends[i] - block_counts[i] - 1) for i in range(N)]
    print(" ".join(result))
main()

Submission status: Time Limit Exceeded

Solution code:
class union():
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.friends = [0 for i in range(n)]
        self.blocks = [[] for i in range(n)]
        self.counts = [1] * n
        self.block_counts = [0] * n
    def find(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.find(self.par[n])
    def block(self, a, b):
        self.blocks[a].append(b)
        self.blocks[b].append(a)
        if self.same(a, b):
            self.block_counts[a] += 1
            self.block_counts[b] += 1
    def unite(self, a, b):
        x = self.find(a)
        y = self.find(b)
        self.friends[a] += 1
        self.friends[b] += 1
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, a, b):
        return self.find(a) == self.find(b)
    def optimize(self):
        self.par = list(map(self.find, self.par))
        for i in range(self.n):
            self.counts[i] = self.par.count(i)    
def main():
    N, M, K = map(int, input().split())
    AB = [list(map(lambda x:int(x)-1, input().split())) for i in range(M)]
    CD = [list(map(lambda x:int(x)-1, input().split())) for i in range(K)]
    u = union(N)
    for a, b in AB:
        u.unite(a, b)
    for c, d in CD:
        u.block(c, d)
    u.optimize()
    result = [0]*N
    for i in range(N):
        result[i] = u.counts[u.find(i)] - u.friends[i] - u.block_counts[i] - 1
    print(" ".join(map(str, result)))
main()

Submission status: Time Limit Exceeded

Solution code:
class union():
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.friends = [0 for i in range(n)]
        self.blocks = [[] for i in range(n)]
        self.counts = [1] * n
        self.block_counts = [0] * n
    def find(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.find(self.par[n])
    def block(self, a, b):
        self.blocks[a].append(b)
        self.blocks[b].append(a)
    def unite(self, a, b):
        x = self.find(a)
        y = self.find(b)
        self.friends[a] += 1
        self.friends[b] += 1
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, a, b):
        return self.find(a) == self.find(b)
    def optimize(self):
        self.par = list(map(self.find, self.par))
        for i in range(self.n):
            self.counts[i] = self.par.count(i)
            for j in self.blocks[i]:
                if self.same(i, j):
                    self.block_counts[i] += 1
def main():
    N, M, K = map(int, input().split())
    AB = [list(map(lambda x:int(x)-1, input().split())) for i in range(M)]
    CD = [list(map(lambda x:int(x)-1, input().split())) for i in range(K)]
    u = union(N)
    for a, b in AB:
        u.unite(a, b)
    for c, d in CD:
        u.block(c, d)
    u.optimize()
    result = [0]*N
    for i in range(N):
        result[i] = u.counts[u.find(i)] - u.friends[i] - u.block_counts[i] - 1
    print(" ".join(map(str, result)))
main()

Submission status: Time Limit Exceeded

Solution code:
class union():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.friends = [0 for i in range(n)]
        self.blocks = [[] for i in range(n)]
        self.counts = [1] * n
    def find(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.find(self.par[n])
    def block(self, a, b):
        self.blocks[a].append(b)
        self.blocks[b].append(a)
    def unite(self, a, b):
        x = self.find(a)
        y = self.find(b)
        self.friends[a] += 1
        self.friends[b] += 1
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, a, b):
        return self.find(a) == self.find(b)
    def optimize(self):
        self.par = list(map(self.find, self.par))
        for i in range(len(self.par)):
            self.counts[i] = self.par.count(i)
def main():
    N, M, K = map(int, input().split())
    AB = [list(map(lambda x:int(x)-1, input().split())) for i in range(M)]
    CD = [list(map(lambda x:int(x)-1, input().split())) for i in range(K)]
    u = union(N)
    for a, b in AB:
        u.unite(a, b)
    for c, d in CD:
        u.block(c, d)
    u.optimize()
    result = [0]*N
    for i in range(N):
        work = 0
        for j in u.blocks[i]:
            if u.same(i, j):
                work += 1
        result[i] = u.counts[u.find(i)] - u.friends[i] - work - 1
    print(" ".join(map(str, result)))
main()

Submission status: Time Limit Exceeded

Solution code:
class union():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.friends = [0 for i in range(n)]
        self.blocks = [[] for i in range(n)]
    def find(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.find(self.par[n])
    def block(self, a, b):
        self.blocks[a].append(b)
        self.blocks[b].append(a)
    def unite(self, a, b):
        x = self.find(a)
        y = self.find(b)
        self.friends[a] += 1
        self.friends[b] += 1
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, a, b):
        return self.find(a) == self.find(b)
    def optimize(self):
        self.par = list(map(self.find, self.par))
def main():
    N, M, K = map(int, input().split())
    AB = [list(map(lambda x:int(x)-1, input().split())) for i in range(M)]
    CD = [list(map(lambda x:int(x)-1, input().split())) for i in range(K)]
    u = union(N)
    for a, b in AB:
        u.unite(a, b)
    for c, d in CD:
        u.block(c, d)
    u.optimize()
    result = [0]*N
    for i in range(N):
        work = 0
        for j in u.blocks[i]:
            if u.same(i, j):
                work += 1
        result[i] = u.par.count(u.find(i)) - u.friends[i] - work - 1
    print(" ".join(map(str, result)))
main()

Submission status: Time Limit Exceeded

Solution code:
class union():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.friends = [0 for i in range(n)]
        self.blocks = [[] for i in range(n)]
    def find(self, n):
        if self.par[n] == n:
            return n
        else:
            return self.find(self.par[n])
    def block(self, a, b):
        self.blocks[a].append(b)
        self.blocks[b].append(a)
    def unite(self, a, b):
        x = self.find(a)
        y = self.find(b)
        self.friends[a] += 1
        self.friends[b] += 1
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, a, b):
        return self.find(a) == self.find(b)
    def optimize(self):
        self.par = list(map(self.find, self.par))
N, M, K = map(int, input().split())
AB = [list(map(lambda x:int(x)-1, input().split())) for i in range(M)]
CD = [list(map(lambda x:int(x)-1, input().split())) for i in range(K)]
u = union(N)
for a, b in AB:
    u.unite(a, b)
for c, d in CD:
    u.block(c, d)
u.optimize()
result = []
for i in range(N):
    work = 0
    for j in u.blocks[i]:
        if u.same(i, j):
            work += 1
    result.append(u.par.count(u.find(i)) - u.friends[i] - work - 1)
print(" ".join(map(str, result)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,k=map(int,input().split())
flag=[0]*(n+1)
friend=[[] for i in range(n+1)]
block=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int, input().split())
    friend[a].append(b)
    friend[b].append(a)

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

d=deque()
m=1
for i in range(1,n+1):
    if flag[i]==0:
        d.append(i)
        flag[i]=m
        while len(d)>0:
            a=d.popleft()
            for j in range(len(friend[a])):
                if flag[friend[a][j]]!=m:
                    flag[friend[a][j]]=m
                    d.append(friend[a][j])
        m+=1
#print(flag)
#print(friend)
#print(block)
answer=[0]*n
for i in range(1,n+1):
    a=sum(x==flag[i] for x in flag)
    b=len(friend[i])+1
    c=0
    for x in range(1,n+1):
        if flag[x]==flag[i] and (x in block[i]):
            c+=1
    #print(a,b,c)
    answer[i-1]=a-b-c

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

Submission status: Time Limit Exceeded

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

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

for m in range(M):
    a,b = map(lambda x:int(x)-1,input().split(" "))
    friend[a].append(b)
    friend[b].append(a)
for k in range(K):
    c,d = map(lambda x:int(x)-1,input().split(" "))
    block[c].append(d)
    block[d].append(c)

group_list = [-1 for i in range(N)]
group_no = 0
group_dict = {}
for i in range(N):
    if group_list[i] ==-1:
        group_list[i] = group_no
        queue = [i]
        q = 0
        visit = [0 for i in range(N)]
        visit[i] = 1
        while True:
            pop = queue[q]
            for j in friend[pop]:
                if visit[j] !=1:
                    queue.append(j)
                    visit[j] = 1
                    group_list[j] = group_no
            q += 1
            if len(queue) == q:
                break
        group_dict[group_no] = queue
        group_no += 1
for i in range(N):
    no = group_list[i]
    queue = group_dict[no]
    frbl_sum = 0
    for j in block[i]:
        if j in queue:
            frbl_sum += 1
    print(len(queue) - frbl_sum -1 -len(friend[i]),end = " ")

Submission status: Time Limit Exceeded

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

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

for m in range(M):
    a,b = map(lambda x:int(x)-1,input().split(" "))
    friend[a].append(b)
    friend[b].append(a)
for k in range(K):
    c,d = map(lambda x:int(x)-1,input().split(" "))
    block[c].append(d)
    block[d].append(c)

group_list = [-1 for i in range(N)]
group_no = 0
group_dict = {}
for i in range(N):
    if group_list[i] ==-1:
        group_list[i] = group_no
        queue = [i]
        q = 0
        visit = [0 for i in range(N)]
        visit[i] = 1
        while True:
            pop = queue[q]
            for j in friend[pop]:
                if visit[j] !=1:
                    queue.append(j)
                    visit[j] = 1
                    group_list[j] = group_no
            q += 1
            if len(queue) == q:
                break
        group_dict[group_no] = queue
        group_no += 1
for i in range(N):
    no = group_list[i]
    queue = group_dict[no]
    frbl_sum = 0
    for j in queue:
        if j in friend[i]:
            frbl_sum += 1
        elif j in block[i]:
            frbl_sum += 1
    print(len(queue) - frbl_sum -1,end = " ")

Submission status: Time Limit Exceeded

Solution code:
nmk_list = input().split(" ")
N = int(nmk_list[0])
M = int(nmk_list[1])
K = int(nmk_list[2])

n_list =[[0 for j in range(N)] for i in range(N)]

for m in range(M):
    ab = input().split(" ")
    a = int(ab[0])-1
    b = int(ab[1])-1
    n_list[a][b] = 1
    n_list[b][a] = 1
for k in range(K):
    cd = input().split(" ")
    c = int(cd[0])-1
    d = int(cd[1])-1
    n_list[c][d] = -1
    n_list[d][c] = -1

graph_group = [-1 for i in range(N)]
group_no = 0

for i in range(N):
    if graph_group[i] == -1:
        queue = [i]
        visit = [0 for num in range(N)]
        visit[i] = 1
        graph_group[i] = group_no
        q = 0
        while True:
            pop = queue[q]
            for j in range(N):
                if n_list[pop][j] == 1 and visit[j] == 0:
                    queue.append(j)
                    visit[j] = 1
                    graph_group[j] = group_no
            q += 1
            if len(queue) == q:
                break
        frbl_sum = 0
        for j in queue:
            if n_list[i][j] != 0:
                frbl_sum += 1
        print(q-frbl_sum-1,end = " ")
        group_no += 1
    else:
        group_no = graph_group[i]
        q = graph_group.count(group_no)
        frbl_sum = 0
        for j in range(N):
            if n_list[i][j] !=0 and graph_group[j] == group_no:
                frbl_sum += 1
        print(q-frbl_sum-1,end = " ")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

# Union Findデータ構造


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

group = UnionFind(n)

friends_dict = {}
block_dict = {}
for i in range(n):
    friends_dict[i] = []
    block_dict[i] = []

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

    group.union(a, b)
    friends_dict[min(a, b)].append(max(a, b))


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

# print(friends_dict)
# print(block_dict)

for i in range(group.n):
    count = 0
    for j in range(group.n):
        if i == j:
            continue
        if max(i, j) in friends_dict[min(i, j)]:
            continue
        if max(i, j) in block_dict[min(i, j)]:
            continue
        if not group.same(i, j):
            continue
        count += 1
    print(count, "", 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


def main():
    N, M, K = map(int, input().split())
    friends = [[] for _ in range(N)]
    blocks = [[] for _ in range(N)]
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a-1].append(b-1)
        friends[b-1].append(a-1)
        uf.union(a-1, b-1)
    for _ in range(K):
        a, b = map(int, input().split())
        blocks[a-1].append(b-1)
        blocks[b-1].append(a-1)

    groups = uf.all_group_members().values()
    ans = [0 for _ in range(N)]

    for i in range(N):
        cnt = uf.size(i) - 1
        for j in blocks[i]:
            if uf.same(i, j):
                cnt -= 1
        for j in friends[i]:
            if uf.same(i, j):
                cnt -= 1
        ans[i] = cnt
            
    print(' '.join(list(map(str, ans))))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


def main():
    N, M, K = map(int, input().split())
    blocks = [[False for _ in range(N)] for _ in range(N)]
    friends = [[] for _ in range(N)]
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a-1].append(b-1)
        friends[b-1].append(a-1)
        uf.union(a-1, b-1)
    for _ in range(K):
        a, b = map(int, input().split())
        blocks[a-1][b-1] = True
        blocks[b-1][a-1] = True

    groups = uf.all_group_members().values()
    ans = [0 for _ in range(N)]

    for group in groups:
        for s in group:
            cnt = 0
            for g in group:
                if s == g:
                    continue
                if g in friends[s]:
                    continue
                if blocks[s][g]:
                    continue
                cnt += 1
            ans[s] = cnt
    
    print(' '.join(list(map(str, ans))))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().strip().split())
# friend = [list(map(int, input().split())) for _ in range(m)]
friend=[[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().strip().split())
    a-=1; b-=1
    friend[a].append(b)
    friend[b].append(a)

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

def dfs(i,color):
    stack=[i] # root
    visited=[False]*n
    while stack:
        v=stack.pop()
        visited[v]=True
        label[v]=color
        for child in friend[v]:
            if visited[child] == False and child not in stack:
                stack.append(child)

label=[None]*n
color=0
colorCnt=[]
for i in range(n):
    if label[i] is None:
        dfs(i,color)
        colorCnt.append(label.count(color))
        color+=1
for i in range(n):
    ans=colorCnt[label[i]]-len(friend[i])-1 # self
    for j in block[i]:
        if label[j]==label[i]:
            ans-=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500*500) # default 1000

n, m, k = map(int, input().strip().split())
# friend = [list(map(int, input().split())) for _ in range(m)]
friend=[[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().strip().split())
    a-=1; b-=1
    friend[a].append(b)
    friend[b].append(a)

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

def dfs(i,color):
    stack=[i] # root
    visited=[False]*n
    while stack:
        v=stack.pop()
        visited[v]=True
        label[v]=color
        for child in friend[v]:
            if visited[child] == False and child not in stack:
                stack.append(child)

label=[None]*n
color=0
for i in range(n):
    if label[i] is None:
        dfs(i,color)
        color+=1
for i in range(n):
    ans=label.count(label[i])-len(friend[i])-1 # self
    for j in block[i]:
        if label[j]==label[i]:
            ans-=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().strip().split())
# friend = [list(map(int, input().split())) for _ in range(m)]
friend=[[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().strip().split())
    a-=1; b-=1
    friend[a].append(b)
    friend[b].append(a)

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

def dfs(i):
    cnt=0
    stack=[i] # root
    visited=[False]*n
    while stack:
        v=stack.pop()
        visited[v]=True
        if v!=i and v not in friend[i] and v not in block[i]:
            cnt+=1
        for child in friend[v]:
            if visited[child] == False and child not in stack:
                stack.append(child)
    return cnt
# def dfs(i):
#     global cnt
#     visited[i]=True
#     if i!=root and i not in friend[root] and i not in block[root]:
#         cnt+=1
#     for child in friend[i]:
#         if visited[child]==False:
#             dfs(child)

for i in range(n):
    # stack=0
    # root=i
    # cnt=0
    # visited=[False]*n
    #-len(friend[i])
    print(dfs(i))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500*500) # default 1000

n, m, k = map(int, input().strip().split())
# friend = [list(map(int, input().split())) for _ in range(m)]
friend=[[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().strip().split())
    a-=1; b-=1
    friend[a].append(b)
    friend[b].append(a)

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

def dfs(i):
    global cnt
    visited[i]=True
    if i!=root and i not in friend[root] and i not in block[root]:
        cnt+=1
    for child in friend[i]:
        if visited[child]==False:
            dfs(child)

for i in range(n):
    # stack=0
    root=i
    cnt=0
    visited=[False]*n
    dfs(i)#-len(friend[i])
    print(cnt)

Submission status: Time Limit Exceeded

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

def main():
    n, m, k = map(int, input().split())
    parent_f = list(range(n+1))
    rank_f = [0]*(n+1)
    parent_b = list(range(n+1))
    rank_b = [0]*(n+1)
    group_f = [set() for _ in range(n+1)]
    group_b = [set() for _ in range(n+1)]
    group_index_f = [None]*(n+1)
    group_index_b = [None]*(n+1)
    friends = [set() for i in range(n+1)]
    blocks = [set() for i in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        friends[a] |= {b}
        friends[b] |= {a}
        unite(a, b, parent_f, rank_f)
    for _ in range(k):
        c, d = map(int, input().split())
        blocks[c] |= {d}
        blocks[d] |= {c}
        unite(c, d, parent_b, rank_b)
    for i in range(1, n+1):
        rf = root(i, parent_f)
        rb = root(i, parent_b)
        group_f[rf] |= {i}
        group_b[rb] |= {i}
        group_index_f[i] = rf
        group_index_b[i] = rb
    for i in range(1, n+1):
        print(len(group_f[group_index_f[i]]-friends[i]-blocks[i]-{i}))
    

def root(x, parent):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x], parent)
    return parent[x]

def unite(x, y, parent, rank):
    x = root(x, parent)
    y = root(y, parent)
    if x != y:
        if rank[x] > rank[y]:
            parent[y] = x
        elif rank[x] < rank[y]:
            parent[x] = y
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    main()