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:
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)
block = [[0 for i in range(n)] for i in range(n)]
count = [-1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1][b-1] = 1
    block[b-1][a-1] = 1
for i in range(k):
    c,d = map(int,input().split())
    block[c-1][d-1] = 1
    block[d-1][c-1] = 1
for i in range(n):
    for j in range(n):
        if uf.same(i,j) and block[i][j] == 0:
            count[i] += 1
print(" ".join(map(str,count)))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
s1=set()
s2=set()
uf=UnionFind(n+1)
for i in range(m):
  a,b=map(int,input().split())
  if a>b:
    a,b=b,a
  s1.add((a,b))
  uf.unite(a,b)
for j in range(k):
  c,d=map(int,input().split())
  if c>d:
    c,d=d,c
  s2.add((c,d))
ans=[]
for i in range(1,n+1):
  cnt=0
  for j in uf.members(i):
    x,y=i,j
    if x>y:
      x,y=y,x
    if not((x,y) in s1 or (x,y) in s2):
      cnt+=1
  ans.append(cnt-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 unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
s=set()
uf=UnionFind(n+1)
for i in range(m):
  a,b=map(int,input().split())
  s.add((a,b))
  s.add((b,a))
  uf.unite(a,b)
for j in range(k):
  c,d=map(int,input().split())
  s.add((c,d))
  s.add((d,c))
ans=[]
for i in range(1,n+1):
  cnt=0
  for j in uf.members(i):
    if not((i,j) in s):
      cnt+=1
  ans.append(cnt-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque

# =============================================================================
# with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#     N ,M ,K = map(int,f.readline().split())
#     A = [list(map(int,f.readline().split())) for _ in range(M)]
#     C = [list(map(int,f.readline().split())) for _ in range(K)]
# =============================================================================
def main():
    N ,M ,K = map(int,input().split())
    A = [list(map(int,input().split())) for _ in range(M)]
    C = [list(map(int,input().split())) for _ in range(K)]
    connection = {i:[] for i in range(1,N+1)}
    seen = {i:False for i in range(1,N+1)}
    label = {i:0 for i in range(1,N+1)}
    todo = deque()
    num = 0
    minus = {i:0 for i in range(1,N+1)}
    
    for pair in A:
        connection[pair[0]].append(pair[1])
        connection[pair[1]].append(pair[0])
        minus[pair[0]] -= 1
        minus[pair[1]] -= 1
        
    while False in seen.values():
        num+=1
        H = [k for k,v in seen.items() if v == False][0]
        todo.append(H)
        seen[H] = True
        group = set()
        while len(todo) > 0:
            current = todo.pop()
            label[current] = num
            group.add(current)
            for i in connection[current]:
                if seen[i] == False:
                    todo.append(i)
                    seen[i] = True
                    
        #print(group)
    
    for pair in C:
        if label[pair[0]] == label[pair[1]]:
            minus[pair[0]] -= 1
            minus[pair[1]] -= 1
    accompany = {i:0 for i in range(1,num+1)}
    for i in range(1,N+1):
        accompany[label[i]] += 1
    
    for i in range(1,N+1):
        print(accompany[label[i]] + minus[i]-1)
    
if __name__ == "__main__":
    main()
# =============================================================================
# A = {5:[5,4],4:[2,3]}
# A[5].append(6)
# del A[5][0]
# =============================================================================

# =============================================================================
#     block = 0
#     for block in C:
#         if block[0] in group and block in group:
#             cone_num -= 2
# =============================================================================

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
import sys
# =============================================================================
# with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#     N ,M ,K = map(int,f.readline().split())
#     A = [list(map(int,f.readline().split())) for _ in range(M)]
#     C = [list(map(int,f.readline().split())) for _ in range(K)]
# =============================================================================
input = sys.stdin.readline
N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = {i:[] for i in range(1,N+1)}
seen = {i:False for i in range(1,N+1)}
label = {i:0 for i in range(1,N+1)}
todo = deque()
All = 0
num = 0
minus = {i:0 for i in range(1,N+1)}

for pair in A:
    connection[pair[0]].append(pair[1])
    connection[pair[1]].append(pair[0])
    minus[pair[0]] -= 1
    minus[pair[1]] -= 1
    
while False in seen.values():
    num+=1
    H = [k for k,v in seen.items() if v == False][0]
    todo.append(H)
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for i in connection[current]:
            if seen[i] == False:
                todo.append(i)
                seen[i] = True
                
    #print(group)

for pair in C:
    if label[pair[0]] == label[pair[1]]:
        minus[pair[0]] -= 1
        minus[pair[1]] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(1,N+1):
    accompany[label[i]] += 1

for i in range(1,N+1):
    print(accompany[label[i]] + minus[i]-1)
    

# =============================================================================
# A = {5:[5,4],4:[2,3]}
# A[5].append(6)
# del A[5][0]
# =============================================================================

# =============================================================================
#     block = 0
#     for block in C:
#         if block[0] in group and block in group:
#             cone_num -= 2
# =============================================================================

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
import sys
# =============================================================================
# with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#     N ,M ,K = map(int,f.readline().split())
#     A = [list(map(int,f.readline().split())) for _ in range(M)]
#     C = [list(map(int,f.readline().split())) for _ in range(K)]
# =============================================================================
input = sys.stdin.readline
N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = {i:[] for i in range(1,N+1)}
seen = {i:False for i in range(1,N+1)}
label = {i:0 for i in range(1,N+1)}
todo = deque()
All = 0
num = 0

for pair in A:
    connection[pair[0]].append(pair[1])
    connection[pair[1]].append(pair[0])
    

while False in seen.values():
    num+=1
    H = [k for k,v in seen.items() if v == False][0]
    todo.append(H)
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for i in connection[current]:
            if seen[i] == False:
                todo.append(i)
                seen[i] = True
                
    #print(group)
minus = {i:0 for i in range(1,N+1)}
for pair in A:
    minus[pair[0]] -= 1
    minus[pair[1]] -= 1
for pair in C:
    if label[pair[0]] == label[pair[1]]:
        minus[pair[0]] -= 1
        minus[pair[1]] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(1,N+1):
    accompany[label[i]] += 1

for i in range(1,N+1):
    print(accompany[label[i]] + minus[i]-1)
    

# =============================================================================
# A = {5:[5,4],4:[2,3]}
# A[5].append(6)
# del A[5][0]
# =============================================================================

# =============================================================================
#     block = 0
#     for block in C:
#         if block[0] in group and block in group:
#             cone_num -= 2
# =============================================================================

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
# =============================================================================
# with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#     N ,M ,K = map(int,f.readline().split())
#     A = [list(map(int,f.readline().split())) for _ in range(M)]
#     C = [list(map(int,f.readline().split())) for _ in range(K)]
# =============================================================================

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = {i:[] for i in range(1,N+1)}
seen = {i:False for i in range(1,N+1)}
label = {i:0 for i in range(1,N+1)}
todo = deque()
All = 0
num = 0

for pair in A:
    connection[pair[0]].append(pair[1])
    connection[pair[1]].append(pair[0])
    

while False in seen.values():
    num+=1
    H = [k for k,v in seen.items() if v == False][0]
    todo.append(H)
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for i in connection[current]:
            if seen[i] == False:
                todo.append(i)
                seen[i] = True
                
    #print(group)
minus = {i:0 for i in range(1,N+1)}
for pair in A:
    minus[pair[0]] -= 1
    minus[pair[1]] -= 1
for pair in C:
    if label[pair[0]] == label[pair[1]]:
        minus[pair[0]] -= 1
        minus[pair[1]] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(1,N+1):
    accompany[label[i]] += 1

for i in range(1,N+1):
    print(accompany[label[i]] + minus[i]-1)
    

# =============================================================================
# A = {5:[5,4],4:[2,3]}
# A[5].append(6)
# del A[5][0]
# =============================================================================

# =============================================================================
#     block = 0
#     for block in C:
#         if block[0] in group and block in group:
#             cone_num -= 2
# =============================================================================

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def same_union_list(self, x):
        l = []
        for i in range(len(self.parent)):
            if i != x:
                if self.same(x, i):
                    l.append(i)
        
        return l

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

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

CD = []
for k in range(K):
    [c, d] = [int(i) for i in input().split()]
    CD.append((c, d))

uf_tree = UnionFindTree(N)
friends = {}

for (a, b) in AB:
    a -= 1
    b -= 1
    if a not in friends:
        friends[a] = []
    if b not in friends:
        friends[b] = []
    friends[a].append(b)
    friends[b].append(a)
    uf_tree.unite(a, b)

candidates = []
#print(uf_tree.parent)
#print(uf_tree.rank)
#print(friends)
#print(blocks)
for n in range(N):
    same_union_list = uf_tree.same_union_list(n)
    #print('{}\'s union_list: {}'.format(n, same_union_list))
    candidates.append(len(same_union_list))

for (a, b) in AB:
    a -= 1
    b -= 1
    candidates[a] -= 1
    candidates[b] -= 1

for (c, d) in CD:
    c -= 1
    d -= 1
    if uf_tree.same(c, d):
        candidates[c] -= 1
        candidates[d] -= 1

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans) - 1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
# =============================================================================
# with open('C:/Users/naoki/Desktop/Atcoder/input.txt') as f:
#     N ,M ,K = map(int,f.readline().split())
#     A = [list(map(int,f.readline().split())) for _ in range(M)]
#     C = [list(map(int,f.readline().split())) for _ in range(K)]
# =============================================================================

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]

seen = {i:False for i in range(1,N+1)}
label = {i:0 for i in range(1,N+1)}
todo = deque()
All = 0
num = 0
while False in seen.values():
    num+=1
    H = [k for k,v in seen.items() if v == False][0]
    todo.append(H)
    seen[H] = True
    group = set()
    while len(todo) > 0:
        current = todo.pop()
        label[current] = num
        group.add(current)
        for connection in A:
            if connection[0] in group and connection[1] in group:
                continue
            elif connection[0] in group and seen[connection[1]] == False:
                todo.append(connection[1])
                seen[connection[1]] = True
            elif connection[1] in group and seen[connection[0]] == False:
                todo.append(connection[0])
                seen[connection[0]] = True

minus = {i:0 for i in range(1,N+1)}
for pair in A:
    minus[pair[0]] -= 1
    minus[pair[1]] -= 1
for pair in C:
    if label[pair[0]] == label[pair[1]]:
        minus[pair[0]] -= 1
        minus[pair[1]] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(1,N+1):
    accompany[label[i]] += 1

for i in range(1,N+1):
    print(accompany[label[i]] + minus[i]-1)
    

# =============================================================================
# A = {5:[5,4],4:[2,3]}
# A[5].append(6)
# del A[5][0]
# =============================================================================

# =============================================================================
#     block = 0
#     for block in C:
#         if block[0] in group and block in group:
#             cone_num -= 2
# =============================================================================

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(2147483647)


class Graph:
    def __init__(self):
        self.graph = defaultdict(set)

    def interconnect(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs(self, start):
        seen = set()
        return self.dfs_recurse(start, seen)

    def dfs_recurse(self, v, seen):
        seen.add(v)
        for u in self.graph[v] - seen:
            self.dfs_recurse(u, seen)
        return seen


if __name__ == "__main__":
    n, m, k = map(int, input().split())

    friends = Graph()
    blocked = defaultdict(set)

    [friends.interconnect(*map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    for _ in range(k):
        c, d = map(lambda x: int(x) - 1, input().split())
        blocked[c].add(d)
        blocked[d].add(c)

    visited = [False] * n
    counts = [0] * n

    for v in range(n):
        if visited[v]:
            continue
        elems = friends.dfs(v)
        elems_cnt = len(elems)
        for i in elems:
            counts[i] = elems_cnt - len(elems & friends.graph[i]) - len(elems & blocked[i]) - 1
            visited[i] = True

    print(*counts)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
   
def main():
    def search_root(v):
        while v != root[v]: v = root[v]
        return v

    N, M, K = list(map(int, input().split()))
    friend = [0] * N
    root = [i for i in range(N)]
    size = [1] * N

    for i in range(M):
        A, B = list(map(int, input().split()))
        A -= 1; B -= 1

        friend[A] += 1
        friend[B] += 1
        r = A

        A = search_root(A)
        B = search_root(B)
        
        if A != B:
            size[A] += size[B]
            root[B] = A
            if size[A] > 10: 
                while r != root[r]: r, root[r] = root[r], A

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

    for i in range(K):
        C, D = list(map(int, input().split()))
        C -= 1; D -= 1

        block[C].add(D)
        block[D].add(C)

    r = [search_root(i) for i in range(N)]

    for i in range(N):
        v = r[i]
        
        ans = size[v]-1-friend[i]
        
        for u in block[i]:
            if r[u] == v: ans -= 1
        print(ans, '', end='')
    print()
         
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(2147483647)


class Graph:
    def __init__(self):
        self.graph = defaultdict(set)

    def interconnect(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs(self, start):
        seen = set()
        return self.dfs_recurse(start, seen)

    def dfs_recurse(self, v, seen):
        seen.add(v)
        for u in self.graph[v] - seen:
            self.dfs_recurse(u, seen)
        return seen

    def size(self, v):
        return len(self.dfs(v))


if __name__ == "__main__":
    n, m, k = map(int, input().split())

    f = Graph()
    b = Graph()

    [f.interconnect(*map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    [b.interconnect(*map(lambda x: int(x) - 1, input().split())) for _ in range(k)]

    visited = [False] * n
    counts = [0] * n

    for v in range(n):
        if visited[v]:
            continue
        elems = f.dfs(v)
        elems_cnt = len(elems)
        for i in elems:
            counts[i] = elems_cnt - len(elems & f.graph[i]) - len(elems & b.graph[i]) - 1
            visited[i] = True

    print(*counts)

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

f = [[False]*(N+1) for _ in range(N+1)]
for i in friend:
    f[i[0]][i[1]] = True
    f[i[1]][i[0]] = True

b = [[False]*(N+1) for _ in range(N+1)]
for i in block:
    b[i[0]][i[1]] = True
    b[i[1]][i[0]] = True
    
stack=deque()
linkList = []
ans = []
visited = [0] * (N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    cnt = 0
    link = [i]
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in range(i,N+1):
            if f[n][j] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.append(j)
    linkList.append(link)

for i in range(1,N+1):
    #連結成分のサイズ
    linkSize = 0
    #「友達関係」または「ブロック関係」はマイナスする
    minus = 0
    for link in linkList:
        if not i in link:
            continue
        for j in link:
            linkSize = len(link)
            if f[i][j] or b[i][j]:
                minus += 1
    ans.append(linkSize-minus-1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import time, sys
sys.setrecursionlimit(int(1e7))

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

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    visited[x] = True
    cycle.append(x)
    for i in friends[x]:
        if not visited[i]:
            dfs(i)
    return


for i, v in enumerate(visited):
    if v:
        continue
    cycle = []
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])


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

for i in count:
    print(i, end=" ")

Submission status: Time Limit Exceeded

Solution code:
import time

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

friends = [[] for i in range(n)]
cands = [None for i in range(n)]
cycles = []
visited = [False for i in range(n)]
count = [0 for i in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].append(b)
    friends[b].append(a)

def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    cycle.append(x)
    for i in friends[x]:
        dfs(i)
    return

time.sleep(3)

for i, v in enumerate(visited):
    if v:
        continue
    cycle = []
    dfs(i)
    l = len(cycle)
    ind = len(cycles)
    cycles.append(cycle)
    for fr in cycle:
        cands[fr] = ind
        count[fr] = l - 1 - len(friends[fr])


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

for i in count:
    print(i, end=" ")

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
    if a < b:
        Frends[a].append(b)
    else:
        Frends[b].append(a)

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

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        t = -1

        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            if i in g and f in g:
                if t < 0:
                    t = j              
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    fglen -= 1
            elif not (i in g or f in g):
                j += 1
                continue
            else:
                if t < 0:
                    if i in g:
                        g.add(f)
                    else:
                        g.add(i)

                    t = j
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    fglen -= 1
            j += 1

        if t < 0:
            fg.append(set([i, f]))

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand[i] += 1
                    cand[f] += 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
    if a < b:
        Frends[a].append(b)
    else:
        Frends[b].append(a)

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

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        t = -1

        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            if i in g and f in g:
                if t < 0:
                    t = j              
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    fglen -= 1
            elif not (i in g or f in g):
                j += 1
                continue
            else:
                if t < 0:
                    if i in g:
                        g.add(f)
                    else:
                        g.add(i)

                    t = j
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    fglen -= 1
            j += 1
            
        if t < 0:
            fg.append(set([i, f]))

# 友人候補を抽出
cand = []
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand.append((i, f,))

# 友人候補をカウント
ans = [0 for _ in range(N)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

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