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())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())

l=list(range(N+1))
r=[0]*(N+1)
la=N
di=[[]for _ in range(N+1)]
def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
    else:
        l[X]=l[Y]
        if r[X]==r[Y]:
            r[Y]+=1

for i in range(M):
    union(a[i],b[i])
    di[a[i]].append(b[i])
    di[b[i]].append(a[i])
for i in range(K):
    di[c[i]].append(d[i])
    di[d[i]].append(c[i])

for i in range(N+1):
    l[i]=find(i)
t=[]
for i in range(N+1):
    w=0
    for j in range(len(di[i])):
        if l[i]==l[di[i][j]]:
            w+=1
    p=l.count(l[i])-1-w

    t.append(p)


print(" ".join(map(str, t[1:])))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
relate = [[0] * N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    relate[a][b] = 1
    relate[b][a] = 1
from collections import deque
# g : グラフ
# 例 [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]]
# i : 始点
def bfs(s):

    #訪れたかどうか
    d = [False] * N
    #初期設定
    que = deque()
    que.append(relate[s])
    d[s] = True
    
    while que:
        p = que.popleft()
        for i, j in enumerate(p):
            if j == 0 or d[i]:
                continue
            else:
                d[i] = True
                que.append(relate[i])
    return d
import copy
d = [bfs(i) for i in range(N)]
block_d = copy.deepcopy(d)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    block_d[a][b] = 0
    block_d[b][a] = 0
for i in range(N):
    d[i][i] = 0
    block_d[i][i] = 0
    print(sum(block_d[i]) - sum(relate[i]))

Submission status: Time Limit Exceeded

Solution code:
N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())

l=list(range(N+1))
r=[0]*(N+1)
la=N

def find(x):
    if l[x]==x:
        return x
    else:
        return find(l[x])

def union(x,y):
    X=find(x)
    Y=find(y)
    if r[X]>r[Y]:
        l[Y]=l[X]
    else:
        l[X]=l[Y]
        if r[X]==r[Y]:
            r[Y]+=1

for i in range(M):
    union(a[i],b[i])

for i in range(N+1):
    l[i]=find(i)
t=[]
for i in range(N+1):
    p=l.count(l[i])-1
    indexes = [j for j, x in enumerate(a) if x == i]
    for j in range(len(indexes)):
        if l[b[indexes[j]]] == l[i]:
            p -= 1
    indexes = [j for j, x in enumerate(b) if x == i]
    for j in range(len(indexes)):
        if l[a[indexes[j]]] == l[i]:
            p -= 1
    indexes = [j for j, x in enumerate(d) if x == i]
    for j in range(len(indexes)):
        if l[c[indexes[j]]] == l[i]:
            p -= 1
    indexes = [j for j, x in enumerate(c) if x == i]
    for j in range(len(indexes)):
        if l[d[indexes[j]]] == l[i]:
            p -= 1
    t.append(p)

print(" ".join(map(str, t[1:])))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
relate = [[0] * N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    relate[a][b] = 1
    relate[b][a] = 1
from collections import deque
# g : グラフ
# 例 [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8]]
# i : 始点
def bfs(s):

    #訪れたかどうか
    d = [False] * N
    #初期設定
    que = deque()
    que.append(relate[s])
    d[s] = True
    
    while que:
        p = que.popleft()
        for i, j in enumerate(p):
            if j == 0 or d[i]:
                continue
            else:
                d[i] = True
                que.append(relate[i])
    return d
import copy
d = [bfs(i) for i in range(N)]
block_d = copy.deepcopy(d)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    block_d[a][b] = 0
    block_d[b][a] = 0
for i in range(N):
    d[i][i] = 0
    block_d[i][i] = 0
    print(sum(block_d[i]) - sum(relate[i]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def dfs(v, seen, overall, connected_components):
    seen[v] = True
    connected_components.add(v)
    for nv in overall[v]:
        if seen[nv] == True:continue
        dfs(nv, seen, overall, connected_components)
def main():
    N, M, K = map(int, input().split())
    overall = {}
    friends = {}
    blocks = {}
    for i in range(N):
        overall[i] = set()
        friends[i] = set()
        blocks[i] = set()
    for _ in range(M):
        a, b = map(int, input().split())
        overall[a-1].add(b-1)
        overall[b-1].add(a-1)
        friends[a-1].add(b-1)
        friends[b-1].add(a-1)
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c-1].add(d-1)
        blocks[d-1].add(c-1)
    ans = {}
    seen = [False] * N
    for i in range(N):
        if seen[i] == True:continue
        connected_components = set()
        dfs(i, seen, overall, connected_components)
        for v in list(connected_components):
            ans[v] = connected_components - {v}
    for i in range(N):
        print(len(ans[i]-friends[i]-blocks[i]), end=" ")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

S = input().split(" ")
N = int(S[0])
M = int(S[1])
K = int(S[2])
ARR = []
BRR = []
for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])

for i in range(K):
    BRR.append([int(s) for s in input().split(" ")])


def prepare(n, arr):
    nodes = [[] for i in range(n)]
    nodeStates = [False for i in range(n)]
    nodeLabels = [0 for i in range(n)]
    for ar in arr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].append(toNode)
        nodes[toNode].append(fromNode)

    return nodes, nodeStates, nodeLabels

def prepare2(n,brr):
    nodes = [[] for i in range(n)]
    for ar in brr:
        fromNode = ar[0] - 1
        toNode = ar[1] - 1
        nodes[fromNode].append(toNode)
        nodes[toNode].append(fromNode)

    return nodes


def calculate(n, m, k, nodes, nodeStates, nodeLabels):
    q = deque()

    label = 0
    labelDict = {}
    while nodeStates.count(False) > 0:

        falseIndex = nodeStates.index(False)

        q.append(falseIndex)

        while len(q) > 0:
            node = q.popleft()
            if nodeStates[node] == True:
                continue
            nodeStates[node] = True
            nodeLabels[node] = label
            childNodes = nodes[node]
            if labelDict.get(label) == None:
                labelDict.__setitem__(label,1)
            else:
                labelDict.__setitem__(label,labelDict.get(label)+1)

            for childNode in childNodes:
                if nodeStates[childNode] == False:
                    q.append(childNode)
        label = label + 1


    result = []
    for i in range(n):
        l = nodeLabels[i]
        s = 0

        for blockNode in blockNodes[i]:
            if nodeLabels[blockNode] == l:
                s = s + 1
        result.append(str(labelDict[l] - len(nodes[i]) - 1 - s))

    print(" ".join(result))


nodes, nodeStates, nodeLabels = prepare(N, ARR)
blockNodes = prepare2(N,BRR)
calculate(N, M, K, nodes, nodeStates, nodeLabels)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    parent = []
    separate = []
    count = []

    def Create(self, N):
        for i in range(N+1):
            self.parent.append(i)
            self.count.append(1)
            self.separate.append(0)

    def Root(self, i):
        if self.parent[i] == i:
            return i
        else:
            return self.Root(self.parent[i])

    def Unite(self, x, y):
        rx = self.Root(x)
        ry = self.Root(y)
        if rx != ry:
            self.parent[rx] = ry
            self.count[ry] += self.count[rx]

    def Same(self, x, y):
        if self.Root(x) == self.Root(y):
            return True
        else:
            return False

    def Devide(self, x, y):
        if self.Same(x, y):
            self.separate[x] += 1
            self.separate[y] += 1

    def Count(self, x):
        c = self.count[self.Root(x)] - 1
        c -= self.separate[x]
        return c


def main():
    n,m,k = list(map(int, input().split()))
    uf = UnionFind()
    uf.Create(n)
    friend = [[] for i in range(n+1)]
    block = [[] for i in range(n+1)]
    ans = [0 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)
        uf.Unite(a,b)
    
    for i in range(k):
        c,d = map(int, input().split())
        uf.Devide(c,d)
    
    for i in range(1,n+1):
        ans[i] = uf.Count(i) - len(friend[i])

    for i in range(1,n+1):
        print(ans[i],end="")
        if i != n:
            print(" ",end="")

    print()
main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    parent = []
    separate = []
    count = []

    def Create(self, N):
        for i in range(N+1):
            self.parent.append(i)
            self.count.append(1)
            self.separate.append([])

    def Root(self, i):
        if self.parent[i] == i:
            return i
        else:
            return self.Root(self.parent[i])

    def Unite(self, x, y):
        rx = self.Root(x)
        ry = self.Root(y)
        if rx != ry:
            self.parent[rx] = ry
            self.count[ry] += self.count[rx]

    def Same(self, x, y):
        if self.Root(x) == self.Root(y):
            return True
        else:
            return False

    def Devide(self, x, y):
        self.separate[x].append(y)
        self.separate[y].append(x)

    def Count(self, x):
        c = self.count[self.Root(x)] - 1
        for i in self.separate[x]:
            if self.Same(x, i) == True:
                c -= 1
        return c


def main():
    n,m,k = list(map(int, input().split()))
    uf = UnionFind()
    uf.Create(n)
    friend = [[] for i in range(n+1)]
    block = [[] for i in range(n+1)]
    ans = [0 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)
        uf.Unite(a,b)
    
    for i in range(k):
        c,d = map(int, input().split())
        uf.Devide(c,d)
    
    for i in range(1,n+1):
        ans[i] = uf.Count(i) - len(friend[i])

    for i in range(1,n+1):
        print(ans[i],end="")
        if i != n:
            print(" ",end="")

    print()
main()

Submission status: Time Limit Exceeded

Solution code:
N, M ,K= map(int, input().split())
a=[0]*M
b=[0]*M
c=[0]*K
d=[0]*K

for i in range(M):
    a[i], b[i] = map(int, input().split())
for i in range(K):
    c[i], d[i] = map(int, input().split())
l=[-1]*(N+1)
la=N

for i in range(M):
    if l[a[i]]<0 and l[b[i]]<0:
        l[a[i]]=la
        l[b[i]]=la
        la-=1
    elif l[a[i]]>l[b[i]]:
        if l[b[i]]>0:
            l=[x if x is not l[b[i]] else l[a[i]] for x in l ]
        else:
            l[b[i]]=l[a[i]]

    else:
        if l[a[i]] > 0:
            l = [x if x is not l[a[i]] else l[b[i]] for x in l]
        else:
            l[a[i]]=l[b[i]]

t=[]

for i in range(1,N+1):

    if l[i]>0:
        p=l.count(l[i])-1
        indexes = [j for j, x in enumerate(a) if x == i]
        for j in range(len(indexes)):
            if l[b[indexes[j]]]==l[i]:
                p-=1
        indexes = [j for j, x in enumerate(b) if x == i]
        for j in range(len(indexes)):
            if l[a[indexes[j]]] == l[i]:
                p -= 1
        indexes = [j for j, x in enumerate(d) if x == i]
        for j in range(len(indexes)):
            if l[c[indexes[j]]] == l[i]:
                p -= 1
        indexes = [j for j, x in enumerate(c) if x == i]
        for j in range(len(indexes)):
            if l[d[indexes[j]]] == l[i]:
                p -= 1


    else:
        p=0
    t.append(p)

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

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    par = []

    def Create(self, N):
        for i in range(N+1):
            self.par.append(i)

    def Root(self, i):
        if self.par[i] == i:
            return i
        else:
            return self.Root(self.par[i])

    def Unite(self, x, y):
        rx = self.Root(x)
        ry = self.Root(y)
        if rx != ry:
            self.par[rx] = ry

    def Same(self, x, y):
        if self.Root(x) == self.Root(y):
            return True
        else:
            return False


def main():
    n,m,k = list(map(int, input().split()))
    uf = UnionFind()
    uf.Create(n)
    friend = [[] for i in range(n+1)]
    block = [[] for i in range(n+1)]
    ans = [0 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)
        uf.Unite(a,b)
    
    for i in range(k):
        c,d = map(int, input().split())
        block[c].append(d)
        block[d].append(c)
    
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            if j in friend[i]:
                continue
            if j in block[i]:
                continue
            if uf.Same(i,j):
                ans[i] += 1
                ans[j] += 1

    for i in range(1,n+1):
        print(ans[i],end="")
        if i != n:
            print(" ",end="")

    print()
main()

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from collections import deque

N,M,K=[int(s) for s in input().split()]
EDGE=[set() for _ in range(N)]
BLOCK=[set() for _ in range(N)]
for _ in range(M):
  a,b=[int(s) for s in input().split()]
  EDGE[a-1].add(b-1)
  EDGE[b-1].add(a-1)
for _ in range(K):
  a,b=[int(s) for s in input().split()]
  BLOCK[a-1].add(b-1)
  BLOCK[b-1].add(a-1)
edge=copy.deepcopy(EDGE)  
  
CONNECT=[0 for _ in range(N)]
  
def dfs(start):
  reach=deque([start])
  while reach:
    _from=reach.popleft()
    for _to in EDGE[_from]:
      EDGE[_to].remove(_from)
      if not(_to in reach) and CONNECT[_to]==0:
        reach.append(_to)
        CONNECT[_to]=CONNECT[_from]
    
treenum=1
ans=[-1 for _ in range(N)]
for i in range(N):
  if CONNECT[i]==0:
    CONNECT[i]=treenum
    dfs(i)
    treenum+=1
  a=CONNECT[i]
  for j in range(N):
    if CONNECT[j]==a and (not(j in edge[i])) and (not(j in BLOCK[i])):
      ans[j]+=1
  
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque

N,M,K=[int(s) for s in input().split()]
EDGE=[set() for _ in range(N)]
BLOCK=[set() for _ in range(N)]
for _ in range(M):
  a,b=[int(s) for s in input().split()]
  EDGE[a-1].add(b-1)
  EDGE[b-1].add(a-1)
for _ in range(K):
  a,b=[int(s) for s in input().split()]
  BLOCK[a-1].add(b-1)
  BLOCK[b-1].add(a-1)
  
CONNECT=[0 for _ in range(N)]
  
def dfs(start):
  reach=deque([start])
  while reach:
    _from=reach.popleft()
    for _to in EDGE[_from]:
      if not(_to in reach) and CONNECT[_to]==0:
        reach.append(_to)
        CONNECT[_to]=CONNECT[_from]
    
treenum=1
ans=[-1 for _ in range(N)]
for i in range(N):
  if CONNECT[i]==0:
    CONNECT[i]=treenum
    dfs(i)
    treenum+=1
  a=CONNECT[i]
  for j in range(N):
    if CONNECT[j]==a and (not(j in EDGE[i])) and (not(j in BLOCK[i])):
      ans[j]+=1
      
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
group_id = {i:[] for i in range(1, N+1)}
group = {}
isChecked = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
g = 0
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    isChecked[i] = 1
    group_id[i] = g
    x = [i]
    ch = child[i].copy()
    while ch:
        c = ch.pop(0)
        if isChecked[c]:
            continue
        group_id[c] = g
        isChecked[c] = 1
        x.append(c)
        ch = list(set(ch) | set(child[c]) - set(x))
    group[g] = len(x)
    g += 1

for i in range(1, N+1):
    ans[i] = group[group_id[i]] - len(child[i]) - 1

for _ in range(K):
    c, d = map(int, input().split())
    if group_id[c] == group_id[d]:
        ans[c] -= 1
        ans[d] -= 1
        
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
group_id = {i:[] for i in range(1, N+1)}
group = {}
isChecked = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
X = []
g = 0
i = 1
while len(X) != N:
    if isChecked[i]:
        i += 1
        continue
    isChecked[i] = 1
    group_id[i] = g
    x = [i]
    ch = child[i].copy()
    while ch:
        c = ch.pop(0)
        group_id[c] = g
        isChecked[c] = 1
        x.append(c)
        ch = list(set(ch) | set(child[c]) - set(x))        
    group[g] = len(x)
    X += x
    g += 1
    i += 1

for i in range(1, N+1):
    ans[i] = group[group_id[i]] - len(child[i]) - 1

for _ in range(K):
    c, d = map(int, input().split())
    if group_id[c] == group_id[d]:
        ans[c] -= 1
        ans[d] -= 1
        
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
group_id = {i:[] for i in range(1, N+1)}
group = {}

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
X = set(range(1, N+1))
g = 0
while X:
    i = X.pop()
    group_id[i] = g
    x = {i}
    ch = set(child[i])
    while ch:
        c = ch.pop()
        group_id[c] = g
        ch = (ch | set(child[c])) - set(x)
        x = x | {c}
    group[g] = len(x)
    X = X - set(x)
    g += 1

for i in range(1, N+1):
    ans[i] = group[group_id[i]] - len(child[i]) - 1

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

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
group_id = {i:[] for i in range(1, N+1)}
group = {}

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
X = set(range(1, N+1))
g = 0
while X:
    i = X.pop()
    group_id[i] = g
    x = {i}
    ch = set(child[i])
    while ch:
        c = ch.pop()
        group_id[c] = g
        ch = (ch | set(child[c])) - set(x)
        x = x | {c}
    group[g] = x
    X = X - set(x)
    g += 1

for i in range(1, N+1):
    ans[i] = len(group[group_id[i]]) - len(child[i]) - 1

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

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N, M, K = map(int, input().split())
ans = np.zeros((N+1,), dtype=int)
child = {i:[] for i in range(1, N+1)}
isBlocked = {i:[] for i in range(1, N+1)}
group = np.zeros((N+1,))

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

for i in range(1, N+1):
    ans[i] = ans[i] - len(child[i]) - 1 
    
X = set(range(1, N+1))
g = 0
while X:
    i = X.pop()
    x = {i}
    ch = set(child[i])
    while ch:
        c = ch.pop()
        ch = (ch | set(child[c])) - set(x)
        x = x | {c}
    ans[list(x)] += len(x)
    group[list(x)] = g
    X = X - set(x)
    g += 1
        
for _ in range(K):
    c, d = map(int, input().split())
    if group[c] == group[d]:
        ans[c] -= 1
        ans[d] -= 1

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
ans = []
child = {i:[] for i in range(1, N+1)}
isBlocked = {i:[] for i in range(1, N+1)}

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

for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].append(d)
    isBlocked[d].append(c)
    
for i in range(1, N+1):
    x = [i]
    ch = set(child[i])
    while ch:
        c = ch.pop()
        ch = (ch | set(child[c])) - set(x)
        x.append(c)
    ans.append(len(set(x) - set(isBlocked[i])) - 1 - len(child[i]))
    
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
relfr={i:set() for i in range(n)}
relbl={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for i in range(k):
  a,b=map(int,input().split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
frsiz={i:len(relfr[i]) for i in range(n)}
cand={0}
searched=set()
gr=set()
all_gr={i for i in range(n)}
ans=[0]*n
c=0
while True:
  siz=0
  while True:
    now=cand.pop()
    gr.add(now)
    c+=1
    siz+=1
    for point in relfr[now].difference(gr,cand):
      cand.add(point)
    if len(cand)==0:
      break
  for i in gr:
    ans[i]=siz-frsiz[i]-len(relbl[i].intersection(gr))-1
    searched.add(i)
  all_gr=all_gr.difference(searched)
  gr.clear()
  if c!=n:
    cand.add(list(all_gr)[0])
  else:
    break
print(' '.join(map(str,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={i:set() for i in range(n)}
relbl={i: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)
frsiz={i:len(relfr[i]) for i in range(n)}
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=[0]*n
c=0
while True:
  siz=0
  while True:
    now=cand.pop()
    gr.add(now)
    c+=1
    siz+=1
    for point in relfr[now].difference(gr,cand):
      cand.add(point)
    if len(cand)==0:
      break
  for i in gr:
    ans[i]=siz-frsiz[i]-len(relbl[i].intersection(gr))-1
    searched.add(i)
  all_gr=all_gr.difference(searched)
  gr.clear()
  if c!=n:
    cand.add(list(all_gr)[0])
  else:
    break
print(' '.join(map(str,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={i:set() for i in range(n)}
relbl={i: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=[0]*n
c=0
while True:
  while True:
    now=cand.pop()
    gr.add(now)
    c+=1
    for point in relfr[now].difference(gr,cand):
      cand.add(point)
    if len(cand)==0:
      break
  for i in gr:
    ans[i]=len(gr)-len(relfr[i])-len(relbl[i].intersection(gr))-1
    searched.add(i)
  all_gr=all_gr.difference(searched)
  gr.clear()
  if c!=n:
    cand.add(list(all_gr)[0])
  else:
    break
print(' '.join(map(str,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=[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=[0]*n
c=0
while True:
  while True:
    now=cand.pop()
    gr.add(now)
    c+=1
    for point in relfr[now].difference(gr,cand):
      cand.add(point)
    if len(cand)==0:
      break
  for i in gr:
    ans[i]=len(gr)-len(relfr[i])-len(relbl[i].intersection(gr))-1
    searched.add(i)
  all_gr-=searched
  gr.clear()
  if c!=n:
    cand.add(list(all_gr)[0])
  else:
    break
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    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()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M, K = MAP()
friend = [LIST() for i in range(M)]
block = [LIST() for i in range(K)]

tree = UnionFind(N)

straight_friend = defaultdict(list)
straight_block = defaultdict(list)

for a, b in friend:
    tree.union(a-1, b-1)
    straight_friend[a-1].append(b-1)
    straight_friend[b-1].append(a-1)

for c, d in block:
    straight_block[c-1].append(d-1)
    straight_block[d-1].append(c-1)

for i in range(N):
    # print(tree.members(i))
    # print(straight_block[i])
    # print(straight_friend[i])
    ans = len(set(tree.members(i)) - set(straight_block[i]) - set((straight_friend[i]))) - 1
    # print(ans)
    # ans = ans - len(straight_friend[i]) - 1
    print(ans, end=" ")

print()

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
c=0
while True:
  while len(cand)!=0:
    now=cand.pop()
    gr.add(now)
    c+=1
    for point in relfr[now]-(relfr[now]&gr)-(relfr[now]&cand):
      cand.add(point)
  for i in gr:
    ans[i]=str(len(gr)-len(relfr[i])-len(relbl[i]&gr)-1)
    searched.add(i)
  all_gr-=searched
  gr.clear()
  if c!=n:
    cand.add(list(all_gr)[0])
  else:
    break
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=[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]-(relfr[now]&gr)-(relfr[now]&cand):
      cand.add(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.add(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=[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]-(relfr[now]&gr)-(relfr[now]&set(cand)):
      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))