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

GRAPH = [[0]*n for _ in range(n)]
BLOCK = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    GRAPH[a][b] = GRAPH[b][a] = 1

for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    BLOCK[a][b] = BLOCK[b][a] = 1

def make_dfs():
    visited = [0]*n

    def dfs(v):
        visited[v] = 1
        for v2 in range(n):
            if not GRAPH[v][v2]:
                continue
            if visited[v2]:
                continue
            dfs(v2)
        return visited
    return dfs


ans = []
for i in range(n):
    f = make_dfs()
    friends = f(i)
    follow = GRAPH[i]
    block = BLOCK[i]
    bl = sum(f and b for f, b in zip(friends, block))

    ans.append(sum(friends) - (sum(follow)+bl)-1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  if uf.same(a-1, b-1):
    block_list[a-1].append(b-1)
    block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(len(uf.members(i)) - len(block_list[i]))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
C=[]
D=[]
for i in range(k):
    c,d=map(int,input().split())
    C.append(c)
    D.append(d)
union=[]
for i in range(n):
    br=0
    for j in range(len(union)):
        if i+1 in set(union[j]):
            br=1
            break
    if br==1:
        continue
    fri=[i+1]
    mark=[0]
    while 0 in set(mark):
        for s in range(len(fri)):
            if mark[s]==0:
                for t in range(m):
                    if A[t]==fri[s] and B[t] not in set(fri):
                        fri.append(B[t])
                        mark.append(0)
                    if B[t]==fri[s] and A[t] not in set(fri):
                        fri.append(A[t])
                        mark.append(0)
                mark[s]=1
    union.append(fri)
unionsize=[]
for i in range(len(union)):
    unionsize.append(len(union[i]))
counter=[]
for i in range(n):
    counter.append(0)

for i in range(m):
    counter[A[i]-1]+=1
    counter[B[i]-1]+=1
for i in range(k):
    for j in range(len(union)):
        if C[i] in union[j] and D[i] in union[j]:
            counter[C[i]-1]+=1
            counter[D[i]-1]+=1
            break

for i in range(n):
    for j in range(len(union)):
        if i+1 in union[j]:
            print(unionsize[j]-counter[i]-1,end=" ")
            break

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
C=[]
D=[]
for i in range(k):
    c,d=map(int,input().split())
    C.append(c)
    D.append(d)
union=[]
for i in range(n):
    br=0
    for j in range(len(union)):
        if i+1 in set(union[j]):
            br=1
            break
    if br==1:
        continue
    fri=[i+1]
    mark=[0]
    while 0 in set(mark):
        for s in range(len(fri)):
            if mark[s]==0:
                for t in range(m):
                    if A[t]==fri[s] and B[t] not in set(fri):
                        fri.append(B[t])
                        mark.append(0)
                    if B[t]==fri[s] and A[t] not in set(fri):
                        fri.append(A[t])
                        mark.append(0)
                mark[s]=1
    union.append(fri)
counter=[]
for i in range(n):
    counter.append(0)

for i in range(m):
    counter[A[i]-1]+=1
    counter[B[i]-1]+=1
for i in range(k):
    for j in range(len(union)):
        if C[i] in union[j] and D[i] in union[j]:
            counter[C[i]-1]+=1
            counter[D[i]-1]+=1
            break

for i in range(n):
    for j in range(len(union)):
        if i+1 in union[j]:
            print(len(union[j])-counter[i]-1,end=" ")
            break

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        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 set(self):
      [self.find(self.parents[i]) for i in range(self.n)]
      
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(len(uf.members(i)) - (len(uf.members(i)+block_list[i])-len(set(uf.members(i)+block_list[i]))))
print(*ans)

Submission status: Time Limit Exceeded

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

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にする
            x, y = y, x

        self.parents[x] += self.parents[y] #xの要素数はyの要素数ぶん増える
        self.parents[y] = x #yをxの子にする

    def size(self, x): #xの属するグループの要素数
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じグループか判定
        return self.find(x) == self.find(y)

    def members(self, x): #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): #print用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

U=UnionFind(n)
M=[[] for i in range(n)]
K=[[] for i in range(n)]

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

ans=[]
for i in range(n):
    s=U.members(i)
    m=M[i]
    k=K[i]
    ans.append(len(s)-len(m)-len(k)-1)
print(*ans)

Submission status: Time Limit Exceeded

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

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にする
            x, y = y, x

        self.parents[x] += self.parents[y] #xの要素数はyの要素数ぶん増える
        self.parents[y] = x #yをxの子にする

    def size(self, x): #xの属するグループの要素数
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じグループか判定
        return self.find(x) == self.find(y)

    def members(self, x): #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): #print用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

U=UnionFind(n)
M=[[] for i in range(n)]
K=[[] for i in range(n)]

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

for i in range(n):
    s=U.members(i)
    m=M[i]
    k=K[i]
    ans=len(s)-len(m)-len(k)-1
    print(ans,end=" ")

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        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 set(self):
      [self.find(self.parents[i]) for i in range(self.n)]
      
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
uf.set()
ans = []
for i in range(N):
  ans.append(len([j for j in uf.members(i) if not j in block_list[i]]))
print(*ans)

Submission status: Time Limit Exceeded

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

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にする
            x, y = y, x

        self.parents[x] += self.parents[y] #xの要素数はyの要素数ぶん増える
        self.parents[y] = x #yをxの子にする

    def size(self, x): #xの属するグループの要素数
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じグループか判定
        return self.find(x) == self.find(y)

    def members(self, x): #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): #print用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    
class Graph():
    def __init__(self): #ノードのつながりを辞書型で表現する
        self.dict = {}
    
    def add_edge(self, v1, v2): #ノード同士をつなぐ
        self.dict[v1].append(v2)
        self.dict[v2].append(v1)

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

U=UnionFind(n)
M=[[] for i in range(n)]
K=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    U.union(a,b)
    M[a].append(b)
    M[b].append(a)
    
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    K[a].append(b)
    K[b].append(a)

for i in range(n):
    s=U.members(i)
    m=M[i]
    ans=len(s)-len(m)-1
    for k in K[i]:
        if k in s:
            ans-=1
    print(ans,end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
def main():
    n,m,k=map(int,input().split())
    friend=[[] for i in range(n)]
    block=[[] for i in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        friend[a-1].append(b)
        friend[b-1].append(a)
    for _ in range(k):
        c,d=map(int,input().split())
        block[c-1].append(d)
        block[d-1].append(c)

    def DFS(G,v,p):
        log=[False]*n
        log[v-1]=True
        q=deque()
        q.append((v,p))
        ans=0
        while q:
            V,P=q[-1]
            for new_v in G[V-1]:
                if new_v==P:continue
                if log[new_v-1]==True:continue
                log[new_v-1]=True
                if new_v not in friend[v-1] and new_v not in block[v-1]:ans+=1
                q.append((new_v,V))
                break
            else:
                q.pop()

        return ans

    ans=[]
    for i in range(n):
        ans.append(DFS(friend,i+1,-1))
    print(*ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

def DFS(G,v,p):
    log=[False]*n
    log[v-1]=True
    q=deque()
    q.append((v,p))
    ans=0
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            if new_v==P:continue
            if log[new_v-1]==True:continue
            log[new_v-1]=True
            if new_v not in friend[v-1] and new_v not in block[v-1]:
                ans+=1
            q.append((new_v,V))
            break
        else:
            q.pop()

    return ans

n,m,k=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)]


friend=Graph(ab)
block=Graph(cd)
#print(friend,block,sep='\n')

ans=[]
for i in range(n):
    ans.append(DFS(friend,i+1,-1))

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n #要素数
        self.parents = [-1] * n #親格納配列(親のときは下流の要素数のマイナスを返す)

    def find(self,x):
        if self.parents[x] < 0: #親のとき
            return x
        else:
            self.parents[x] = self.find(self.parents[x]) #再帰で親に繋ぎ変える
            return self.parents[x]

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

        if x == y: #親が同じときスキップ
            return

        if self.parents[x] > self.parents[y]: #要素数が多いほうをxにする
            x, y = y, x

        self.parents[x] += self.parents[y] #xの要素数はyの要素数ぶん増える
        self.parents[y] = x #yをxの子にする

    def size(self, x): #xの属するグループの要素数
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じグループか判定
        return self.find(x) == self.find(y)

    def members(self, x): #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): #print用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

U=UnionFind(n)
M=[[] for i in range(n)]
K=[[] for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    U.union(a,b)
    M[a].append(b)
    M[b].append(a)
    
for i in range(k):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    K[a].append(b)
    K[b].append(a)

for i in range(n):
    s=U.members(i)
    m=M[i]
    ans=len(s)-len(m)-1
    for k in K[i]:
        if k in s:
            ans-=1
    print(ans,end=" ")

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
A=[]
B=[]
for i in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
C=[]
D=[]
for i in range(k):
    c,d=map(int,input().split())
    C.append(c)
    D.append(d)
seq=[]
for i in range(n):
    fri=[i+1]
    mark=[0]
    while 0 in set(mark):
        for s in range(len(fri)):
            if mark[s]==0:
                for t in range(m):
                    if A[t]==fri[s] and B[t] not in set(fri):
                        fri.append(B[t])
                        mark.append(0)
                    if B[t]==fri[s] and A[t] not in set(fri):
                        fri.append(A[t])
                        mark.append(0)
                mark[s]=1
    fri.remove(i+1)
    for t in range(m):
        if A[t]==i+1:
            fri.remove(B[t])
        if B[t]==i+1:
            fri.remove(A[t])
    for s in range(k):
        if C[s]==i+1 and D[s] in set(fri):
            fri.remove(D[s])
    for s in range(k):
        if D[s]==i+1 and C[s] in set(fri):
            fri.remove(C[s])
    seq.append(len(fri))
for i in range(n):
    print(seq[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, M, K = lr()
    fri = [[] for _ in range(N)]
    for i in range(M):
        a, b = lr()
        fri[a-1].append(b-1)
        fri[b-1].append(a-1)
    blo = [[] for _ in range(N)]
    for i in range(K):
        c, d = lr()
        blo[c-1].append(d-1)
        blo[d-1].append(c-1)

    graph = [0 for _ in range(N)]
    for i in range(N):
        vis = [False for _ in range(N)]
        s = [i]
        vis[i] = True
        while len(s) > 0:
            v = s.pop()
            vis[v] = True
            if v in blo[i]:
                graph[i] -= 1
            for j in fri[v]:
                if vis[j]:
                    continue
                s.append(j)
                vis[j] = True
        graph[i] += sum(vis)
    ans = []
    for i in range(N):
        ans.append(graph[i]-len(fri[i])-1)
    print(*ans, sep=' ')
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]

for _ in range(M):
	a, b = map(int, input().split())
	friend[a - 1].append(b - 1)
	friend[b - 1].append(a - 1)
	
for _ in range(K):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
	
# 同じ連結成分にラベルを振る（まだラベルを振っていない = -1 で初期化）
label = [-1] * N

cnt_label_num = 0

for i in range(N):
	if label[i] != -1: continue # もう振ってあったら飛ばす
	
	# 振ってなかったら幅優先でラベルを振る
	Q = [i]
	while Q:
		cur = Q.pop(0)
		if label[cur] != -1: continue
		label[cur] = cnt_label_num
		for adj in friend[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	
	cnt_label_num += 1
	
# お友達候補計算
cnt = Counter(label)
for i in range(N):
	friend_candidate = cnt[label[i]] - 1 # 同じグラフにいる人
	friend_candidate -= len(friend[i]) # 元から友達を引く
	# blockしている人が同じグラフにいるときはその分引く
	for block_man in block[i]:
		if label[i] == label[block_man]:
			friend_candidate -= 1
	print(friend_candidate, end = " ")

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]

for _ in range(M):
	a, b = map(int, input().split())
	friend[a - 1].append(b - 1)
	friend[b - 1].append(a - 1)
	
for _ in range(K):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
	
# 同じ連結成分にラベルを振る（まだラベルを振っていない = -1 で初期化）
label = [-1] * N

cnt_label_num = 0

for i in range(N):
	if label[i] != -1: continue # もう振ってあったら飛ばす
	
	# 振ってなかったら幅優先でラベルを振る
	Q = [i]
	while Q:
		cur = Q.pop(0)
		if label[cur] != -1: continue
		label[cur] = cnt_label_num
		for adj in friend[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	
	cnt_label_num += 1
	
# お友達候補計算
cnt = Counter(label)
for i in range(N):
	friend_candidate = cnt[label[i]] - 1 # 同じグラフにいる人
	friend_candidate -= len(friend[i]) # 元から友達を引く
	# blockしている人が同じグラフにいるときはその分引く
	for block_man in block[i]:
		if label[i] == label[block_man]:
			friend_candidate -= 1
	print(friend_candidate, 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にする
            x, y = y, x

        self.parents[x] += self.parents[y] #xの要素数はyの要素数ぶん増える
        self.parents[y] = x #yをxの子にする

    def size(self, x): #xの属するグループの要素数
        return -self.parents[self.find(x)]

    def same(self, x, y): #同じグループか判定
        return self.find(x) == self.find(y)

    def members(self, x): #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): #print用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

U=UnionFind(n)
M=[]
K=[]
for i in range(n):
    M.append([])
    K.append([])

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    U.union(a,b)
    M[a].append(b)
    M[b].append(a)
    
for i in range(k):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    K[a].append(b)
    K[b].append(a)

for i in range(n):
    S=U.members(i)
    for m in M[i]:
        if m in S:
            S.remove(m)
    for k in K[i]:
        if k in S:
            S.remove(k)
    print(len(S)-1,end=" ")

Submission status: Time Limit Exceeded

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

Frends = [[] for _ in range(N)]
Fs = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Frends[a].append(b)
    Frends[b].append(a)
    if a < b:
        Fs[a].append(b)
    else:
        Fs[b].append(a)

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

# process
# 友人グループを作成
fg = []
for i in range (N):
    l = Fs[i] 
    if len(l) == 0:
        continue

    l.append(i)
    s = set(l)

    t = -1
    j = 0
    fglen = len(fg)
    while j < fglen:
        sfg = s&fg[j]
        if len(sfg) > 0:
            if t < 0:
                t = j
                fg[j] |= s
            else:
                fg[t] |= fg[j]
                fg.pop(j)
                fglen -= 1
        j += 1

    if t < 0:
        fg.append(s)

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for g in fg:
    for f in g:
        cand[f] = len(g)-len(Frends[f])-len(set(Blocked[f])&g)-1

# output
#print(fg)
print(" ".join(map(str, cand)))

Submission status: Time Limit Exceeded

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

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

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

# process
# 友人グループを作成
fg = []
for i in range (N):
    l = [x for x in Frends[i] if x>i]
    if len(l) == 0:
        continue

    l.append(i)
    s = set(l)

    t = -1
    j = 0
    fglen = len(fg)
    while j < fglen:
        sfg = s&fg[j]
        if len(sfg) > 0:
            if t < 0:
                t = j
                fg[j] |= s
            else:
                fg[t] |= fg[j]
                fg.pop(j)
                fglen -= 1
        j += 1

    if t < 0:
        fg.append(s)

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for g in fg:
    for f in g:
        cand[f] = len(g)-len(Frends[f])-len(set(Blocked[f])&g)-1

# output
#print(fg)
print(" ".join(map(str, cand)))

Submission status: Time Limit Exceeded

Solution code:
    #d
    
def main():        
    import sys
    input = sys.stdin.readline
    
    n,m,k = map(int,input().split())
    
    # friends_pair=[]
    # for i in range(m):
    #     a,b = map(int,input().split())
    #     friends_pair.append((a-1,b-1))
    
    # friend=[[] for _ in range(n)]
    # for ab in friends_pair:
    #     a,b = ab
    #     friend[a].append(b)
    #     friend[b].append(a) 
        
    friends_pair=[]
    friend=[[] for _ in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        a-=1
        b-=1
        friends_pair.append((a,b))
        friend[a].append(b)
        friend[b].append(a) 
            
        
    block=[]
    for i in range(k):
        a,b = map(int,input().split())
        block.append((a-1,b-1))
    
    from collections import deque
    clusters=[]
    visited=[0]*n
    list_cluster=[0]*n
    i_c=0
    while sum(visited)<n:
        for i in range(n):
            if visited[i]==0:
                start=i
                break
        
        cluster =[start]
        q=deque([(start,togo) for togo in friend[start]]) #スタート地点から行ける場所を列挙
        visited[start]=1
        list_cluster[start]=i_c
        for togo in friend[start]:
            visited[togo]=1
            cluster.append(togo)
            list_cluster[togo]=i_c
        while q:
            parent,x = q.popleft()
            for y in friend[x]:
                if y == parent:#親ノードを飛ばし
                    continue
                if visited[y]==0:
                    q.append((x,y))#子ノードを追加
                    visited[y]=1
                    cluster.append(y)
                    list_cluster[y]=i_c
    #        print(parent,x,q)
        clusters.append(cluster)
        i_c+=1
    
    ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
    for f0,f1 in friends_pair:
        if list_cluster[f0] ==  list_cluster[f1]:
            ans[f0]-=1
            ans[f1]-=1
    for b0,b1 in block:
        if list_cluster[b0] ==  list_cluster[b1]:
            ans[b0]-=1
            ans[b1]-=1
    print(*ans)

main()