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:
import itertools
import sys

readline = sys.stdin.buffer.readline


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[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.par[x] = y
        else:
            self.par[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 get_size(self, x):
        return -self.par[self.find(x)]


def main():
    N, M, K = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(M)]
    CD = [list(map(int, readline().split())) for _ in range(K)]

    E = UnionFind(N)

    ans = [0 for _ in range(N)]
    for a, b in AB:
        a -= 1
        b -= 1
        E.unite(a, b)
        ans[a] -= 1
        ans[b] -= 1

    for i, j in itertools.combinations(list(range(N)), 2):
        if E.same(i, j):
            ans[i] += 1
            ans[j] += 1

    for i, j in CD:
        i -= 1
        j -= 1
        if E.same(i, j):
            ans[i] -= 1
            ans[j] -= 1

    print(*ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    import queue
    N, M, K = read_values()

    friend = [set() for _ in range(N)]
    friend_num = [0] * N
    for _ in range(M):
        a, b = read_values()
        a -= 1
        b -= 1
        friend[a].add(b)
        friend[b].add(a)
        friend_num[a] += 1
        friend_num[b] += 1

    
    block = [set() for _ in range(N)]
    for _ in range(K):
        a, b = read_values()
        a -= 1
        b -= 1
        block[a].add(b)
        block[b].add(a)

    already = [False] * N
    C = [0] * N
    for i in range(N):
        if already[i]:
            continue
        s = {i}
        q = queue.Queue()
        already[i] = True
        q.put(i)
        while not q.empty():
            k = q.get()
            out = friend[k]
            for l in out:
                if already[l]:
                    continue
                s.add(l)
                q.put(l)
                already[l] = True
        c = len(s)
        for j in s:
            if c > len(block[j]):
                C[j] = c - len([p for p in block[j] if p in s])
            else:
                C[j] = len(s.difference(block[j]))
    res = [str(C[i] - friend_num[i] - 1) for i in range(N)]
    print(" ".join(res))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

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

    def address(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.address()}

    def size(self,x):
        return -self.root[self.Find_Root(x)]


n,m,k=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
CD=[list(map(int,input().split())) for _ in range(k)]

A=UnionFind(n+1)
C=[[] for _ in range(n+1)]
D=[[] for _ in range(n+1)]

for a,b in AB:
    A.Unite(a,b)
    C[a] +=[b]
    C[b] +=[a]

for c,d in CD:
    if A.isSameGroup(c,d):
        D[c] +=[d]
        D[d] +=[c]

ans=[]
for i in range(1,n+1):
    ans +=[len(A.members(i))-len(C[i])-len(D[i])-1]

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,M,K=map(int,input().split())
tn=[0]*N
l=[i for i in range(N)]
for i in range(M):
    A,B=map(lambda x:int(x)-1,input().split())
    t=B
    tn[A]+=1
    tn[B]+=1
    while 1:
        if l[t]==t:
            l[t]=l[A]
            break
        l[t],t=l[A],l[t]
ln=[0]*N
for i in range(N):
    if l[i]!=i:
        c=[i]
        t=l[i]
        while 1:
            if l[t]==t:
                for j in c:
                    l[j]=t
                break
            t=l[t]
        ln[t]+=1
    else:
        ln[i]+=1
for i in range(K):
    C,D=map(lambda x: int(x)-1,input().split())
    if l[C]==l[D]:
        tn[C]+=1
        tn[D]+=1
for i in range(N):
    print(ln[l[i]]-tn[i]-1,end=" ")

Submission status: Time Limit Exceeded

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

class UnionFind:
    def __init__(self, val):
        self.parent = self
        self.val = val
        self.rank = 0

    def get_root(self):
        n = self
        while n.parent is not n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val


friends = []
for i in range(n + 1):
    friends.append(UnionFind(i))

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    x, y = friends[a], friends[b]
    x_root, y_root = x.get_root(), y.get_root()
    if x_root.rank == y_root.rank:
        y_root.parent = x_root
        x_root.rank += 1
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root

block = [[] for _ in range(n + 1)]
for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)


labels = [None] * (n + 1)
for i in range(1, n + 1):
    if labels[i] is None:
        x = friends[i]
        counter = 0
        connected = []
        for j in range(i, n + 1):
            y = friends[j]
            if x.find_set() == y.find_set():
                counter += 1
                connected.append(j)
        for c in connected:
            labels[c] = [i, counter]
ans = []
for i in range(1, n + 1):
    num = labels[i][1] - 1
    for j in graph[i]:
        if labels[i][0] == labels[j][0]:
            num -= 1
    for k in block[i]:
        if labels[i][0] == labels[k][0]:
            num -= 1
    ans.append(num)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

sys.setrecursionlimit(1000000)
N,M,K = map(int,input().split())
graph = collections.defaultdict(set)
block = collections.defaultdict(set)
for _ in range(M):
    a,b =map(int,input().split())
    graph[a].add(b)
    graph[b].add(a)
for _ in range(K):
    a,b =map(int,input().split())
    block[a].add(b)
    block[b].add(a)

counter = collections.defaultdict(set)
dic = {}
def dfs(i,visit,c,start):
    visit.add(i)
    c.add(i)
    dic[i] = start
    for g in graph[i]:
        if g not in visit:
            dfs(g,visit,c,start)
ans = [0]*N
visit =set()
for i in range(N):
    if i + 1 not in visit:
        dfs(i + 1,visit,counter[i+1],i + 1)
    #print(len(counter[dic[i + 1]]))
    tmp = counter[dic[i + 1]] - block[i + 1]
    tmp = tmp - graph[i + 1]
    ans[i] = len(tmp) -1
#print(ans)
for i in range(len(ans) -1):
    print(ans[i], end=" ")
print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque as que
n, m, k = map(int, input().split())
from collections import defaultdict as dd
f_dic = dd(lambda: [])
b_dic = dd(lambda: [])

for i in range(m):
  a, b = map(int, input().split())
  f_dic[a] += [b]
  f_dic[b] += [a]
for i in range(k):
  c, d = map(int, input().split())
  b_dic[c] += [d]
  b_dic[d] += [c]

ans = que()
for i in range(1, n+1):
  #print(friends)
  visited = que([i])
  q = que(f_dic[i][::])
  while len(q) != 0:
    #print(i, visited, q)
    person = q.pop()
    visited.append(person)
    Cands = f_dic[person]
    for cand in Cands:
      if cand not in visited and cand not in q:
        q.append(cand)
  counter = 0
  for blocked in b_dic[i]:
    if blocked in visited:
      counter += 1
  ans.append(len(visited) - 1 - len(f_dic[i]) - counter)
print(*ans, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
friends=[[] for i in range(N)]
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1]*n
  
  def root(self,x):
    if self.parents[x]<0:
      return x
    else:
      return self.root(self.parents[x])
  def unite(self,x,y):
    xp=self.root(x)
    yp=self.root(y)
    if xp==yp:
      return
    if self.parents[xp] > self.parents[yp]:
      xp,yp=yp,xp
    self.parents[xp]+=self.parents[yp]
    self.parents[yp]=xp
    return
  def same(self,x,y):
    return self.root(x)==self.root(y)
  def size(self,x):
    return -self.parents[self.root(x)]
  def members(self, x):
    xp = self.root(x)
    return [i for i in range(self.n) if self.root(i) == xp]
Tree=UnionFind(N)
for i in range(M):
  a,b=map(int,input().split())
  Tree.unite(a-1,b-1)
  friends[a-1].append(b-1)
  friends[b-1].append(a-1)
for i in range(K):
  c,d=map(int,input().split())
  friends[c-1].append(d-1)
  friends[d-1].append(c-1)
print(*[len(set(Tree.members(i))-set(friends[i]))-1 for i in range(N)])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

def root(x):
    while par[x]!=x:
        x=par[x]
    return x

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[y]<size[x]: x,y=y,x  #yの要素数を大きく
    size[x]+=size[y]
    par[y]=x

def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	#隣接で友達関係のカウント

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	#隣接でブロックしている人のカウント
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],

Submission status: Time Limit Exceeded

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

N, M, K = map(int, input().split())
edges = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].add(b)
    edges[b].add(a)

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

visited = [False] * N
cnt = 0

def dfs(u, s):
    if visited[u]:
        return

    visited[u] = True
    for v in edges[u]:
        if visited[v]:
            continue
        if v == s:
            continue

        if v in block_edges[s] or v in edges[s]:
            pass
        else:
            global cnt
            cnt += 1

        dfs(v, s)


ans = []
for i in range(N):
    visited = [False] * N
    cnt = 0
    for v in edges[i]:
        dfs(v, i)
    ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M,K = map(int,input().split())
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())
uni = UnionFind(N)
frd = [0 for i in range(N)]
bl = [[] for i in range(N)]
for i in range(M):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    uni.union(a,b)
    frd[a] +=1
    frd[b] += 1
for i in range(K):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    bl[a].append(b)
    bl[b].append(a)
ans = [0 for i in range(N)]
for i in range(N):
    a = set(uni.members(i)) - set(bl[i])
    print(len(a)-frd[i]-1,end=' ')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

f_lst = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    f_lst[a].append(b)
    f_lst[b].append(a)

b_lst = [[] for _ in range(n+1)]
for i in range(k):
    c,d = map(int,input().split())
    b_lst[c].append(d)
    b_lst[d].append(c)

res = []
for i in range(1, n+1):
    tmp = []
    visited = [False]*(n+1)
    visited[i] = True
    que = deque(f_lst[i])
    while que:
        v = que.popleft()
        if visited[v]:
            continue
        else:
            visited[v] = True
            tmp.append(v)
            for w in f_lst[v]:
                que.append(w)
    res.append(tmp)

ans = []
for i in range(n):
    x,y,z = set(res[i]), set(f_lst[i+1]), set(b_lst[i+1])
    ans.append(len(x-y-z))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

def root(x):
    while par[x]!=x:
        x=par[x]
    return x

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    par[x]=y
    size[y]+=size[x]

def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	#隣接で友達関係のカウント

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	#隣接でブロックしている人のカウント
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M,K = map(int,input().split())
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())
uni = UnionFind(N)
frd = [[] for i in range(N)]
bl = [[] for i in range(N)]
for i in range(M):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    uni.union(a,b)
    frd[a].append(b)
    frd[b].append(a)
for i in range(K):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    bl[a].append(b)
    bl[b].append(a)
ans = [0 for i in range(N)]
for i in range(N):
    a = set(uni.members(i)) - set(bl[i])
    print(len(a)-len(frd[i])-1,sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M,K = map(int,input().split())
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())
uni = UnionFind(N)
frd = [[] for i in range(N)]
bl = [[] for i in range(N)]
for i in range(M):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    uni.union(a,b)
    frd[a].append(b)
    frd[b].append(a)
for i in range(K):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    bl[a].append(b)
    bl[b].append(a)
ans = [0 for i in range(N)]
for i in range(N):
    a = set(uni.members(i)) - set(bl[i])
    ans[i] = len(a)-len(frd[i])-1

print(*ans,sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M,K = map(int,input().split())
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())
uni = UnionFind(N)
frd = [[] for i in range(N)]
bl = [[] for i in range(N)]
for i in range(M):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    uni.union(a,b)
    frd[a].append(b)
    frd[b].append(a)
for i in range(K):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    bl[a].append(b)
    bl[b].append(a)
ans = [0 for i in range(N)]
for i in range(N):
    mem = set(uni.members(i)) - set(frd[i]) - set(bl[i])
    ans[i] = len(mem)-1
print(*ans,sep=' ')

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
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())
uni = UnionFind(N)
frd = [[] for i in range(N)]
bl = [[] for i in range(N)]
for i in range(M):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    uni.union(a,b)
    frd[a].append(b)
    frd[b].append(a)
for i in range(K):
    a,b= map(int,input().split())
    a -= 1
    b -= 1
    bl[a].append(b)
    bl[b].append(a)
ans = [0 for i in range(N)]
for i in range(N):
    mem = set(uni.members(i)) - set(frd[i]) - set(bl[i])
    ans[i] = len(mem)-1
print(*ans,sep=' ')

Submission status: Time Limit Exceeded

Solution code:
n, m, k = list(map(int, input().split()))
friends = [tuple(map(int, input().split())) for _ in range(m)]
block = [tuple(map(int, input().split())) for _ in range(k)]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def get_group(self, x):
        x = self.find(x)
        return set([node+1 for node in range(n) if x == self.find(node+1)])

union_find = UnionFind(n)

for f1, f2 in friends:
    union_find.union(f1, f2)

block_d = {}
for i in range(1, n+1):
    block_d[str(i)] = set()
for b1, b2 in block:
    block_d[str(b1)].add(b2)
    block_d[str(b2)].add(b1)

friends_d = {}
for i in range(1, n+1):
    friends_d[str(i)] = set()
for f1, f2 in friends:
    friends_d[str(f1)].add(f2)
    friends_d[str(f2)].add(f1)

groups = []
for i in range(1, n+1):
    target_group = None
    for group in groups:
        if i in group:
            target_group = group
            break
    if target_group is None:
        target_group = union_find.get_group(i)
    print(len(target_group-block_d[str(i)]-friends_d[str(i)])-1, end=" ")

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    N, M, K = map(int, input().split())
    ans = [0] * N
    table = [[] for i in range(N)]
    visited = [0] * N
    block = [[] for i in range(N)]

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

    for i in range(N):
        if visited[i] == 0:
            Q = deque()
            Q.append(i)
            visited[i] = 1
            group = deque()
            group.append(i)
            while Q:
                x = Q.popleft()
                for y in table[x]:
                    if visited[y] == 0:
                        Q.appendleft(y)
                        visited[y] = 1
                        group.append(y)
            n = len(group)
            for i in range(n):
                x = group[i]
                ans[x] += n - len(table[x]) - 1
                for j in range(i + 1, n):
                    y = group[j]
                    if y in block[x]:
                        ans[x] -= 1
                        ans[y] -= 1
    print(" ".join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parent = [-1 for _ in range(n)]
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数

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

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

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

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

    def is_root(self, x):
        return self.parent[x] < 0

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

friends = []
blocks = []
uf = UnionFind(n)

for _ in range(m):
    array = list(map(int, input().split()))
    uf.unite(array[0]-1, array[1]-1)
    friends.append([array[0]-1, array[1]-1])

for _ in range(k):
    array = list(map(int, input().split()))
    blocks.append([array[0]-1, array[1]-1])

friends.sort()
blocks.sort()

for i in range(n):
    uf.find(i)

friend_list_num = [0] * n

for i in range(n-1):
    for j in range(i+1, n):
        if uf.same(i, j) is True:
            if [i, j] not in friends and [i, j] not in blocks and [j, i] not in friends and [j, i] not in blocks:
                friend_list_num[i] += 1
                friend_list_num[j] += 1

for i in range(n):
    print(friend_list_num[i], end=' ')

Submission status: Time Limit Exceeded

Solution code:
# D 解き直し
# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
n,m,k = map(int, input().split())
block = [[False for j in range(n)] for i in range(n)]
ans = [0 for i in range(n)]
unions = UnionFind(n)
for i in range(m):
    a,b = map(int, input().split())
    block[a-1][b-1] = True
    block[b-1][a-1] = True
    unions.union(a-1, b-1)
for i in range(k):
    a,b = map(int, input().split())
    block[a-1][b-1] = True
    block[b-1][a-1] = True
for i in range(n):
    ms = unions.members(i)
    count = 0
    for m in ms:
        if not(block[i][m]):
            count += 1
    ans[i] = count -1
print(*ans)