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:
#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) 
        
    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 f in friends_pair:
        if list_cluster[f[0]] ==  list_cluster[f[1]]:
            ans[f[0]]-=1
            ans[f[1]]-=1
    for b in block:
        if list_cluster[b[0]] ==  list_cluster[b[1]]:
            ans[b[0]]-=1
            ans[b[1]]-=1
    print(*ans)
    
main()

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) 
        
    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=[]
    # for i in range(n):
    #     friend_cand = [j for j in range(n) if j in clusters[list_cluster[i]] ]
    #     #print(friend_cand)
    #     ans.append( len([ff for ff in friend_cand if ff not in block[i] and ff not in friend[i] ] ) -1)
    
    # same_cluster = [clusters[list_cluster[i]] for i in range(n) ]
    # for i in range(n):
    #     same = same_cluster[i]
    #     ans.append(  len([s for s in same_cluster[i] if s!=i and s not in friend[i] and s not in block[i]]) )
    
    #print(*ans)
    
    ans = [len(clusters[list_cluster[i]])-1 for i in range(n)  ]
    for f in friends_pair:
        if list_cluster[f[0]] ==  list_cluster[f[1]]:
            ans[f[0]]-=1
            ans[f[1]]-=1
    for b in block:
        if list_cluster[b[0]] ==  list_cluster[b[1]]:
            ans[b[0]]-=1
            ans[b[1]]-=1
    print(*ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
from collections import deque
from collections import defaultdict
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, y = y, x

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

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

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

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

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

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

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [set() for _ in range(N)]
blocks = [set() for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    friends[A].add(B)
    friends[B].add(A)
for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    blocks[C].add(D)
    blocks[D].add(C)


ans = []
for n in range(N):
    members = uf.members(n)
    diffs = set(members).difference(friends[n], blocks[n])
    ans.append(len(diffs)-1)

ans = map(str, ans)
print(" ".join(ans))

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):
    fs = Frends[i]
    for f in fs:
        if i > f:
            continue

        t = -1
        s = set([i, f])
        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            sand = s&g
            if t < 0:
                if len(sand) > 0:
                    t = j
                    if sand == s:
                        break
                    elif i in sand:
                        g.add(f)
                    else:
                        g.add(i)

            elif len(sand) > 0:
                #   同一人物を含む友人グループを結合
                fg[t] = fg[t] | g
                fg.pop(j)
                fglen -= 1
            
            j += 1

        if t < 0:
            fg.append(s)

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

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

Submission status: Time Limit Exceeded

Solution code:
def root(parents, i):
    depth = 0
    while parents[i] != i:
        i = parents[i]
        depth += 1

    return i, depth

def isSame(parents, a, b):
    return root(parents,a)[0] == root(parents, b)[0]

def union(parents, size, a, b):
    pa, deptha = root(parents, a)
    pb, depthb = root(parents, b)
    if pa == pb: # already same group
        return
    if deptha < depthb:
        parents[pb] = pa
        size[pa] += size[pb]
    else:
        parents[pa] = pb
        size[pb] += size[pa]

def resolve():
    N, M, K = list(map(int, input().split()))
    parents = [i for i in range(N)]
    size = [1] * N
    ans = [0] * N

    for i in range(M):
        A, B = list(map(int, input().split()))
        ans[A-1] += 1
        ans[B-1] += 1
        union(parents, size, A-1, B-1)

    for i in range(N):
        pi = root(parents, i)[0]
        ans[i] = size[pi] - ans[i] -1 # eliminate friend count from candidate

    for i in range(K):
        A, B = list(map(int, input().split()))
        if isSame(parents, A-1, B-1):
            ans[A-1] -= 1
            ans[B-1] -= 1

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

resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

tb = [[None]*n for i in range(n)]
# 友達登録
for i in range(m):
    tb[fr[i][0]-1][fr[i][1]-1] = 1
    tb[fr[i][1]-1][fr[i][0]-1] = 1
# ブロック登録
for i in range(k):
    tb[br[i][0]-1][br[i][1]-1] = -1
    tb[br[i][1]-1][br[i][0]-1] = -1
# 自分は無視
for i in range(n):
    tb[i][i] = 0

#print("- - - - - - -")
#print(*tb, sep="\n")

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

    for i in range(n):
        #print("-- ",i+1,"の友達候補探し")
        #表の初期化
        g = [None for i in range(n)]

        stack = deque()
        stack.append(i)
        #最初の地点のコストは0
        g[i] = 0

        while stack:
            k = stack.pop() #stackから取り出す
            move = [d for d in range(n) if tb[k][d] == 1]#友達なら移動
            #moveprint = [d+1 for d in range(n) if tb[k][d] == 1]
            #print(k+1, "の友達", moveprint)
            for dk in move:
                if g[dk] == None:
                    g[dk] = 1
                    stack.append(dk)
                    if tb[i][dk] == None:
                        #print(i+1,dk+1,"は友達！")
                        ans[i] += 1
    return ans

#友達を辿ってたどり着けるところまで考える
print(*dfs_check(), sep=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

tb = [[None]*n for i in range(n)]
# 友達登録
for i in range(m):
    tb[fr[i][0]-1][fr[i][1]-1] = 1
    tb[fr[i][1]-1][fr[i][0]-1] = 1
# ブロック登録
for i in range(k):
    tb[br[i][0]-1][br[i][1]-1] = -1
    tb[br[i][1]-1][br[i][0]-1] = -1
# 自分は無視
for i in range(n):
    tb[i][i] = 0

#print("- - - - - - -")
#print(*tb, sep="\n")

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

    for i in range(n):
        #print("-- ",i+1,"の友達候補探し")
        #表の初期化
        g = [None for i in range(n)]

        stack = deque()
        stack.append(i)
        #最初の地点のコストは0
        g[i] = 0

        while stack:
            k = stack.pop() #stackから取り出す
            move = [d for d in range(n) if tb[k][d] == 1]#友達なら移動
            moveprint = [d+1 for d in range(n) if tb[k][d] == 1]
            #print(k+1, "の友達", moveprint)
            for dk in move:
                if g[dk] == None:
                    g[dk] = 1
                    stack.append(dk)
                    if tb[i][dk] == None:
                        #print(i+1,dk+1,"は友達！")
                        ans[i] += 1
    return ans

#友達を辿ってたどり着けるところまで考える
print(*dfs_check(), sep=" ")

Submission status: Time Limit Exceeded

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

n,m,k = map(int,input().split())
ans = [0]*(n+1)
frd = [[] for _ in range(n+1)]

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

ucnt = 0
uni = [-1]*(n+1)
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,0))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if uni[nxt] != -1 or nxt == prev: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for _ in range(k):
    c,d = map(int,input().split())
    if uni[c] == uni[d]:
        ans[c] -= 1
        ans[d] -= 1

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

Submission status: Time Limit Exceeded

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

n,m,k = map(int,input().split())
ans = [0]*n
frd = [[] for _ in range(n)]

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

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if uni[c] == uni[d]:
        ans[c] -= 1
        ans[d] -= 1

for i in range(n): ans[i] += cnt[uni[i]] - 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/03/04

@author: fanta
'''
import time
N,M,K = map(int, input().split())
friends_set = []
enemies_set = []
groups = []
menbers = set()
group_num = -1
bond = []
count = {}
results = {}

start = time.time()

for i in range(M):
    friends_set.append(set(int(x) for x in input().split()))

for i in range(K):
    enemies_set.append(set(int(x) for x in input().split()))

for n in range(N):
    results[n+1] = 0
    count[n+1] = 0

# print(time.time() - start)
# start2 = time.time()

for friend in friends_set:
    if friend.isdisjoint(menbers):
        group_num += 1
        groups.append(set(friend))

    else:
        for v in range(group_num+1):
            if (friend.isdisjoint(groups[v]))^True:
                groups[v] = groups[v] | friend
                bond.append(v)

            if len(bond) > 1:
                groups[bond[0]]= groups[bond[1]] | groups[bond[0]]
                groups[bond[1]].clear()
                group_num = len(groups) - 1
        bond.clear()
    menbers = menbers | friend

# print(time.time() - start2)
# start3 = time.time()

for v in range(group_num+1):
    for friend in friends_set:
        if friend <= groups[v]:
            friend_list = list(friend)
            count[friend_list[0]] += 1
            count[friend_list[1]] += 1

    for enemy in enemies_set:
        if enemy <= groups[v]:
            enemy_list = list(enemy)
            count[enemy_list[0]] += 1
            count[enemy_list[1]] += 1

    group_len = len(groups[v])
    for i in groups[v]:
        results[i] = group_len - 1 - count[i]

# print(time.time() - start3)


for out in results.values():
    print(out,end=' ')

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
  def __init__(self,n):
    self.parent = []
    self.rank = []
    for i in range(n):
      self.parent.append(i)
      self.rank.append(int(1))

  def find(self,n):
    if self.parent[n] == n:
      return self.parent[n]
    else:
      self.parent[n] = self.find(self.parent[n])
      return self.parent[n]

  def unite(self,n,m):
    n = self.find(n)
    m = self.find(m)

    if n == m:
      return
    else:
      if self.rank[n] < self.rank[m]:
        self.parent[n] = m
      elif self.rank[n] > self.rank[m]:
        self.parent[m] = n
      elif self.rank[n] == self.rank[m]:
        self.parent[m] = n
        self.rank[n] += 1




N,M,K = (int(i) for i in input().split())

uft = UnionFindTree(N)

friend = [0] * N
for i in range(M):
  A,B = (int(i) for i in input().split())
  uft.unite(A-1,B-1)
  friend[A-1] += 1
  friend[B-1] += 1


# candidate = [4,3,1]
# candidate => 自分 + 友達 + 友達候補 (include ブロック関係)
for i in range(N):
  uft.find(i)

candidate = []
for i in range(N):
  candidate.append(uft.parent.count(uft.parent[i]))

blocked = [0] * N
for i in range(K):
  C,D = (int(i) for i in input().split())
  if uft.parent[C-1] == uft.parent[D-1]:
    blocked[C-1] += 1
    blocked[D-1] += 1

for i in range(N):
  candidate[i] -= (friend[i]+blocked[i]+1)


print(*candidate)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = []
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]
seenb = [False for _ in range(N)]
def dfs():
    labelb = 1
    while False in seen:
        label = 1
        i = seen.index(False)
        seen[i] = label
        seenb[i] = labelb
        que = deque([i])
        seg = deque([i])
        while que:
            #print(que)
            neci = que.pop()
            for nec in graph[neci]:
                if seen[nec]== False:
                    seen[nec]=label
                    seenb[nec]=labelb
                    que.append(nec)
                    seg.append(nec)
                    label += 1
        for iii in seg:
            seen[iii] = label

        labelb += 1

dfs()
for i in range(N):
    count = seen[i] - 1 -len(graph[i])
    if bgraph[i]:
          for j in bgraph[i]:
                if seenb[i] == seenb[j]:
                    count -= 1
    cnt.append(count)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = []
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]

def dfs():
    
    label = 1
    while False in seen:
        i = seen.index(False)
        seen[i] = label
        que = deque([i])
        while que:
            #print(que)
            neci = que.pop()
            for nec in graph[neci]:
                if seen[nec]== False:
                    seen[nec]=label
                    que.append(nec)
        label += 1


dfs()
for i in range(N):
    count = seen.count(seen[i]) -1 -len(graph[i])
    if bgraph[i]:
        for j in bgraph[i]:
            if seen[i] == seen[j]:
                count -= 1
    cnt.append(count)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:

from collections import deque


N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
#sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = []
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]

def dfs(i):
    #if i not in bgraph[j]:
    #    seen[i]= True
    #else:
    #    seen[i]="block"
    #if graph[i]:
    #    for nec in graph[i]:
    #        if seen[nec] == False:
    #            dfs(nec,j)
    seen[i] = True
    que = deque([i])
    while que:

        neci = que.pop()
        for nec in graph[neci]:
            if seen[nec]== False:
                if nec not in bgraph[i]:
                    seen[nec]=True
                else:
                    seen[nec]="block"
                que.append(nec)

for i_n in range(N):
    seen = [False for _ in range(N)]
    dfs(i_n)
    #print(seen)
    cnt.append(seen.count(True) - 1 - len(graph[i_n]))

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
N,M,K = [int(x) for x in input().split(' ')]

friends = []
blocks = []
exclusions = []
theirs_friends = {x+1:[] for x in range(N)}
already = set()
possible_friends = {x+1:set() for x in range(N)}

for _ in range(M):
    a,b = [int(x) for x in input().split(' ')]
    friends.append((a,b))

for _ in range(K):
    c,d = [int(x) for x in input().split(' ')]
    blocks.append((c,d))

exclusions = friends + blocks

for friend in friends:
    theirs_friends[friend[0]].append(friend[1])
    theirs_friends[friend[1]].append(friend[0])

def search(l, cur_p):
    for p in l:

        if (p,cur_p) not in exclusions and (cur_p, p) not in exclusions:
            possible_friends[p].add(cur_p)
            possible_friends[cur_p].add(p)
            exclusions.append((p,cur_p))
            exclusions.append((cur_p, p))
    
    already.add(cur_p)
    l.append(cur_p)
    
    for next_p in theirs_friends[cur_p]:
        if next_p in l:
            continue
        search(l, next_p)
        

for n in theirs_friends.keys():
    if n in already:
        continue

    search([], n)

print(' '.join([str(len(x)) for x in possible_friends.values()]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

class Uf():
    def __init__(self, n):
        self.par = list(range(N))
 
    def root(self, x):
        if self.par[x] == x:
            return x
        
        root_x = self.root(self.par[x])
        self.par[x] = root_x
        return root_x
    
    def merge(self, a, b):
        root_a, root_b = self.root(a), self.root(b)
        
        if root_a == root_b:
            return
            
        if root_a > root_b:
            root_a, root_b = root_b, root_a
        
        self.par[root_a] = root_b
    
    def isSame(self, a, b):
        return self.root(a) == self.root(b)
    
    def size(self, x):
        return self.par.count(self.par[x])


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

exep = [[] for i in range(N)]

uf = Uf(N)

for i in range(M):
    a, b  = map(int,input().split())
    a, b = a-1, b-1 
    exep[a].append(b)
    exep[b].append(a)
    uf.merge(a, b)

for i in  range(K):
    a, b  = map(int,input().split())
    a, b = a-1, b-1
    if not uf.isSame(a,b):
        continue
    exep[a].append(b)
    exep[b].append(a)

for i in range(N):
    uf.root(i)

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

Submission status: Time Limit Exceeded

Solution code:
class Uf():
    def __init__(self, n):
        self.par = list(range(N))
 
    def root(self, x):
        if self.par[x] == x:
            return x
        
        root_x = self.root(self.par[x])
        self.par[x] = root_x
        return root_x
    
    def merge(self, a, b):
        root_a, root_b = self.root(a), self.root(b)
        
        if root_a == root_b:
            return
            
        if root_a > root_b:
            root_a, root_b = root_b, root_a
        
        self.par[root_a] = root_b
    
    def isSame(self, a, b):
        return self.root(a) == self.root(b)
    
    def size(self, x):
        return self.par.count(self.par[x])


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

exep = [[] for i in range(N)]

uf = Uf(N)

for i in range(M):
    a, b  = map(int,input().split())
    a, b = a-1, b-1 
    exep[a].append(b)
    exep[b].append(a)
    uf.merge(a, b)

for i in  range(K):
    a, b  = map(int,input().split())
    a, b = a-1, b-1
    if not uf.isSame(a,b):
        continue
    exep[a].append(b)
    exep[b].append(a)

for i in range(N):
    uf.root(i)

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

Submission status: Time Limit Exceeded

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

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - len(frd[i]) - 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - len(frd[i]) - 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - 1
    for f in frd[i]:
        if uni[i] == uni[f]: ans -= 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/03/04

@author: fanta
'''
N,M,K = map(int, input().split())
friends_set = []
enemies_set = []
groups = []
menbers = set()
group_num = -1
bond = []
count = {}
results = {}

for i in range(M):
    friends_set.append(set(int(x) for x in input().split()))

for i in range(K):
    enemies_set.append(set(int(x) for x in input().split()))

for n in range(N):
    results[n+1] = 0
    count[n+1] = 0

for friend in friends_set:
    if friend.isdisjoint(menbers):
        group_num += 1
        groups.append(set())
        groups[group_num] = friend

    else:
        for v in range(group_num+1):
            if (friend.isdisjoint(groups[v]))^True:
                groups[v] = groups[v]|friend
                bond.append(v)

            if len(bond) > 1:
                groups[bond[0]]= groups[bond[1]] | groups[bond[0]]
                groups[bond[1]].clear()
                group_num = len(groups) - 1

        bond.clear()

    menbers = menbers|friend



for v in range(group_num+1):
    for friend in friends_set:
        if friend <= groups[v]:
            friend_list = list(friend)
            count[friend_list[0]] += 1
            count[friend_list[1]] += 1

    for enemy in enemies_set:
        if enemy <= groups[v]:
            enemy_list = list(enemy)
            count[enemy_list[0]] += 1
            count[enemy_list[1]] += 1

    group_len = len(groups[v])
    for i in groups[v]:
        results[i] = group_len - 1 - count[i]




for out in results.values():
    print(out,end=' ')