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:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#import math

#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

    def 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())
AB=[list(map(int,input().split())) for i in range(M)]
for i in range(M):
    AB[i][0]-=1
    AB[i][1]-=1
CD=[list(map(int,input().split())) for i in range(K)]
for i in range(K):
    CD[i][0]-=1
    CD[i][1]-=1


uf=UnionFind(N)
for a,b in AB:
    uf.union(a,b)

fblst=[set() for i in range(N)]
for a,b in AB+CD:
    fblst[a].add(b)
    fblst[b].add(a)

dic={}
lst=[0 for i in range(N)]
for i in uf.roots():
    a=set(uf.members(i))
    dic.update({i:a})
    for m in a:
        lst[m]=i

for i in range(len(lst)):
    root=lst[i]
    lst[i]=len(dic[root]-fblst[i])-1

print(" ".join(list(map(str,lst))))

Submission status: Time Limit Exceeded

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce
import sys
sys.setrecursionlimit(1000000)


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

    ary = []
    block = []

    for _ in range(N):
        ary.append(set())
        block.append(set())

    for _ in range(M):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        ary[A].add(B)
        ary[B].add(A)

    for _ in range(K):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        block[A].add(B)
        block[B].add(A)

    def dfs(n, closed):
        closed.add(n)
        for i in ary[n]:
            if not i in closed:
                dfs(i, closed)

    ans = []
    for i in range(N):
        s = set()
        dfs(i, s)
        for j in block[i]:
            s.add(j)
        ans.append(len(s) - len(ary[i]) - len(block[i]) - 1)
        #print(s, len(ary[i]), len(block[i]))
    ans = " ".join(map(str, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

N, M, K = map(int, input().split())
repn = [[] for _ in range(N + 1)]
repnNum = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    repn[a].append(b)
    repn[b].append(a)
    repnNum[a] += 1
    repnNum[b] += 1

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


def cand(i):
    visited = [0] * (N + 1)
    visited[i] = 1
    q = deque([i])
    while q:
        u = q.popleft()
        for v in repn[u]:
            if visited[v] == 0:
                visited[v] = 1
                q.append(v)

    component = []
    num = 0
    for i in range(1, N + 1):
        if visited[i] == 1:
            component.append(i)
            num += 1
    return component, num


preFriend = defaultdict(set)
compNum = defaultdict(int)
for i in range(1, N + 1):
    if i not in preFriend:
        l, number = cand(i)
        for f in l:
            preFriend[f] = set(l)
            compNum[f] = number

ans = []
for i in range(1, N + 1):
    out = 0
    for b in block[i]:
        if b in preFriend[i]:
            out += 1

    ans.append(compNum[i] - out - repnNum[i] - 1)
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
n,m,k = (int(x) for x in input().split())
n_f = []
n_b = []
for i in range(n):
    n_f.append(0)
    n_b.append(0)

#A = []
#B = []
F = [[] for i in range(n)]
for i in range(m):
    a,b = (int(x) for x in input().split())
    #A.append(a)
    #B.append(b)
    F[a-1].append(b-1)
    F[b-1].append(a-1)
    n_f[a-1] += 1
    n_f[b-1] += 1
#C = []
#D = []
#B = [[]]*n
B = [[] for i in range(n)]
for i in range(k):
    a,b = (int(x) for x in input().split())
    #C.append(a)
    #D.append(b)
    B[a-1].append(b-1)
    B[b-1].append(a-1)

#print(F)
tansaku = [False] * n
#counts = [0]*n
vers = [[] for i in range(n)]


for i in range(n):
    if tansaku[i]: continue
    tansaku[i] = True
    #count = 1
    temp = [i]
    ver = [i]
    while(len(temp)>0):
        this = temp[0]
        for j in F[this]:
            if tansaku[j] == True:
                continue
            else:
                tansaku[j] = True
                temp.append(j)
                ver.append(j)
                #count += 1
        temp = temp[1:]
    #print(ver)
    for j in ver:
        vers[j] = ver

#print(vers)
    
out = []
for i in range(n):
    versi = vers[i]
    count = len(versi)-1
    for j in B[i]:
        if j in versi:
            count -= 1
    out.append(str(count - n_f[i]))
print(" ".join(out))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 深さ
        self.size = [1] * n  # size[i]はiを根とするグループのサイズ

    def find(self, x):  # xの親を返す
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])

    def unite(self, x, y):  # x,yの属する集合をマージする
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def same(self, x, y):  # x,yが同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # xが属する集合の大きさを返す
        return self.size[self.find(x)]


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M
C, D = [0] * K, [0] * K

# 全部 0-indexed に合わせる

g_direct =[[] for _ in range(N)]
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    g_direct[min(A[i], B[i])].append(max(A[i], B[i]))
    uf.unite(A[i], B[i])

for i in range(K):
    C[i], D[i] = map(int, input().split())
    C[i] -= 1
    D[i] -= 1
    g_direct[min(C[i], D[i])].append(max(C[i], D[i]))


ans = [0] * N
for i in range(N-1):
    for j in range(i+1, N):
        if j in g_direct[i]:
            continue
        elif uf.same(i, j):  # j が同じ集合に含まれるかチェック
            ans[i] += 1
            ans[j] += 1

print(*ans)

Submission status: Time Limit Exceeded

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

def solve():
    N, M, K = map(int,input().split())
    F = {i:set() for i in range(1,N+1)}
    E = {i:{i,} for i in range(1,N+1)}
    for _ in range(M):
        a, b = map(int,input().split())
        F[a].add(b)
        F[b].add(a)

    for _ in range(K):
        c,d = map(int,input().split())
        E[c].add(d)
        E[d].add(c)

    C = set()
    G = dict()
    P = dict()
    root = filter(lambda x: x not in C, range(1,N+1))

    for i in root:
        q = [i]
        l = set()
        while q:
            v = q.pop()
            l.add(v)
            for u in F[v]:
                if u not in l:
                    q.append(u)
        C |= l
        for v in l:
            P[v] = i
        G[i] = set(l)
    res = ' '.join(map(str, (len(G[P[i]] - E[i]-F[i]) for i in range(1,N+1))))
    return res

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
n,m,k = (int(x) for x in input().split())
n_f = []
n_b = []
#for i in range(n):
#    n_f.append(0)
#    n_b.append(0)

#A = []
#B = []
F = [[] for i in range(n)]
for i in range(m):
    a,b = (int(x) for x in input().split())
    #A.append(a)
    #B.append(b)
    F[a-1].append(b-1)
    F[b-1].append(a-1)
    #n_f[a-1] += 1
    #n_f[b-1] += 1
#C = []
#D = []
#B = [[]]*n
B = [[] for i in range(n)]
for i in range(k):
    a,b = (int(x) for x in input().split())
    #C.append(a)
    #D.append(b)
    B[a-1].append(b-1)
    B[b-1].append(a-1)

#print(F)
tansaku = [False] * n
#counts = [0]*n
vers = [[] for i in range(n)]


for i in range(n):
    if tansaku[i]: continue
    tansaku[i] = True
    #count = 1
    temp = [i]
    ver = [i]
    while(len(temp)>0):
        this = temp[0]
        for j in F[this]:
            if tansaku[j] == True:
                continue
            else:
                tansaku[j] = True
                temp.append(j)
                ver.append(j)
                #count += 1
        temp = temp[1:]
    #print(ver)
    for j in ver:
        vers[j] = ver

#print(vers)
    
out = []
for i in range(n):
    count = len(vers[i])-1
    for j in B[i]:
        if j in vers[i]:
            count -= 1
    out.append(str(count - len(F[i])))
print(" ".join(out))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 深さ
        self.size = [1] * n  # size[i]はiを根とするグループのサイズ

    def find(self, x):  # xの親を返す
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])

    def unite(self, x, y):  # x,yの属する集合をマージする
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def same(self, x, y):  # x,yが同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # xが属する集合の大きさを返す
        return self.size[self.find(x)]


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M
C, D = [0] * K, [0] * K

# 全部 0-indexed に合わせる

g_direct =[[] for _ in range(N)]
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    g_direct[A[i]].append(B[i])
    g_direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

for i in range(K):
    C[i], D[i] = map(int, input().split())
    C[i] -= 1
    D[i] -= 1
    g_direct[C[i]].append(D[i])
    g_direct[D[i]].append(C[i])


ans = [0] * N
for i in range(N-1):
    for j in range(i+1, N):
        if j in g_direct[i]:
            continue
        elif uf.same(i, j):  # j が同じ集合に含まれるかチェック
            ans[i] += 1
            ans[j] += 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

x= [[] for i in range(n)] # 友達関係のグラフ



for i in range(m):
    x[a[i][0]-1].append(a[i][1]-1)
    x[a[i][1]-1].append(a[i][0]-1)

for i in range(k):
    x[c[i][0]-1].append(c[i][1]-1)
    x[c[i][1]-1].append(c[i][0]-1)




# ユニオンファインド
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())

uf=UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)

ans=[]
for i in range(n):
    ans.append(len(uf.members(i))-len(set(uf.members(i))&set(x[i]))-1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

    
from collections import defaultdict

n, m, k = map(int, input().split())
uf = UnionFind(n+1)
friends = defaultdict(list)
block = defaultdict(list)

for _ in range(m):
    a, b = map(int, input().split())
    uf.Unite(a, b)
    friends[a].append(b)
    friends[b].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)

    
members = defaultdict(list)
for i in range(1, n+1):
    r = uf.Find_Root(i)
    members[r].append(i)
    
    
ans = []
for i in range(1, n+1):
    F = friends[i]
    r = uf.Find_Root(i)
    M = members[r]
    B = block[i]
    ans.append(len(set(M) - set(F) - set(B) - set([i])))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

graphs = {}
for i in range(1, n+1):
    graphs[i] = []

for _ in range(m):
    a, b = map(int, input().split(" "))
    graphs[a].append(b)
    graphs[b].append(a)


not_uses = [True] * (n+1)
def get_same_nodes(in_node, gid):
    kids = graphs[in_node]
    same_nodes = []
    for kid in kids:
        if not_uses[kid] is True:
            not_uses[kid] = gid
            same_nodes.append(kid)
            cur_same_nodes = get_same_nodes(kid, gid)
            same_nodes += cur_same_nodes
        else:
            continue
    return same_nodes

def get_graph(start_node, gid):
    not_uses[start_node] = gid
    same_nodes = get_same_nodes(start_node, gid)
    same_nodes.append(start_node)

    n_same_nodes = len(same_nodes)
    cur_kouhos = {}
    for node in same_nodes:
        friends = graphs[node]
        cur_n_friend = len(friends)
        kouho = n_same_nodes - 1 - cur_n_friend
        cur_kouhos[node] = kouho

    return same_nodes, cur_kouhos

graph_i = not_uses

gid = 1
kouhos = {}
for start_node in range(1, n+1):
    if not_uses[start_node] is not True:
        continue

    same_nodes, cur_kouhos = get_graph(start_node, gid) 
    kouhos.update(cur_kouhos)

    gid += 1

#print("kouhos", kouhos)
for _ in range(k):
    c1, c2 = map(int, input().split(" "))
    g1 = graph_i[c1]
    g2 = graph_i[c2]
    if g1 != g2:
        continue

    kouhos[c1] -= 1
    kouhos[c2] -= 1

for node in range(1, n+1):
    print kouhos[node],
print

Submission status: Time Limit Exceeded

Solution code:
a=0
for i in range(10**13):
  a+=1
print(0)

Submission status: Time Limit Exceeded

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

def solve():
    N, M, K = map(int,input().split())
    F = {i:set() for i in range(1,N+1)}
    E = {i:{i,} for i in range(1,N+1)}
    for _ in range(M):
        a, b = map(int,input().split())
        F[a].add(b)
        F[b].add(a)

    for _ in range(K):
        c,d = map(int,input().split())
        E[c].add(d)
        E[d].add(c)

    C = set()
    P = dict()
    root = filter(lambda x: x not in C, range(1,N+1))

    for i in root:
        q = [i]
        l = set()
        while q:
            v = q.pop()
            l.add(v)
            for u in F[v]:
                if u not in l:
                    q.append(u)
        P[i] = set(l)
    res = ' '.join(map(str, (len(P[i] - E[i]-F[i]) for i in range(1,N+1))))
    return res

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
F=[[]for i in range(N)]
B=[[]for i in range(N)]
C=[[]for i in range(N)]
ans=[0]*N
for i in range(M):
    a,b=map(int,input().split())
    F[a-1].append(b-1)
    F[b-1].append(a-1)

for j in range(K):
    a,b=map(int,input().split())
    B[a-1].append(b-1)
    B[b-1].append(a-1)
#print(F)
#print(B)

for i in range(N):
    D=[0]*N
    D[i]=1
    #print(D)
    q=[]
    for obj in F[i]:
        D[obj]=1
        q.append(obj)
    #q=F[i]
    l=len(q)
    while(l>0):
        k=q[0]
        #print(k)
        C[i].append(k)
        for j in F[k]:
            if(D[j]==0):
                q.append(j)
                D[j]=1
        q.pop(0)
        #print(q)
        l=len(q)
    #print("BBB")
#rint(C)
#print(F)
#print(B)
for i in range(N):
    for j in range(len(C[i])):
        k=C[i][j]
        #print(k)
        if(k not in F[i]):
            if(k not in B[i]):
                ans[i]+=1
ans=[str(a) for a in ans]
ans=" ".join(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

x= [[] for i in range(n)] # 友達関係のグラフ
y= [[] for i in range(n)] # ブロック関係のグラフ


for i in range(m):
    x[a[i][0]-1].append(a[i][1]-1)
    x[a[i][1]-1].append(a[i][0]-1)

for i in range(k):
    x[c[i][0]-1].append(c[i][1]-1)
    x[c[i][1]-1].append(c[i][0]-1)




# ユニオンファインド
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())

uf=UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)

ans=[]
for i in range(n):
    ans.append(len(uf.members(i))-len(set(uf.members(i))&set(x[i]))-1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].add(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[{i} for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
#"""
for i in range(n):
    tmp=(l[sans[i]]-block[i])-friends[i]-{i}
    ans[i]=len(tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def dfs(N, E, s):
    stack = [(s, 0)]
    seen = [0]*(N+1)
    seen[s] = 1
    
    while stack:
        v, par = stack.pop()
        for i in E[v]:
            if i == par:
                continue
            elif seen[i] == 0:
                seen[i] = 1
                stack.append((i, v))
    
    return seen

def main():
    N,M,K = map(int, readline().split())

    F = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, readline().split())
        F[a].append(b)
        F[b].append(a)
    
    B = [[] for _ in range(N+1)]
    for _ in range(K):
        c,d = map(int, readline().split())
        B[c].append(d)
        B[d].append(c)


    ans = []
    for i in range(1,N+1):
        tmp = 0
        seen = dfs(N,F,i)
        tmp += sum(seen) - 1
        tmp -= len(F[i])
        for j in B[i]:
            if seen[j] == 1:
                tmp -= 1
        ans.append(tmp)
    
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size)]
        self.rank = [0] * size
 
    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def is_same(self, x, y):  # check two vertices are in the same group
        return self.find(x) == self.find(y)
 
    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # the same group
            return
        # unite a small one to a bigger one to balance trees
        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 main():
    N,M,K = map(int,input().split())
    fris = set()
    for _ in range(M):
        fris.add(tuple(sorted([int(i) -1 for i in input().split()])))
    blos = set()
    for _ in range(K):
        blos.add(tuple(sorted([int(i) -1 for i in input().split()])))
    uf = UnionFind(N)
    for a,b in fris:
        #if a == b-1 or b == a-1:
        uf.unite(a,b)
    alls = fris.union(blos)
    #print(alls)
    countl = []
    cands = set()
    for i in range(N):
        count = 0
        for j in range(N):
            if tuple(sorted([i,j])) in cands:
                count += 1
                continue
            if i == j:
                #print(i,"==",j)
                continue
            if tuple(sorted([i, j])) in alls:
                #print(i,"fri or blo",j)
                continue
            #if i == j -1 or j == i-1:
            #    count += 1
            if uf.is_same(i,j):
                count += 1
                cands.add(tuple(sorted([i,j])))
            #else:
            #    print(i,"else",j)
        countl.append(str(count))
    print(" ".join(countl))

    #print("Yes") if uf.is_same(a, b) else print("No")
    
                

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        #親ノードの番号を格納
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
        self.group = [set([i]) for i 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 same_check(self, x, y):
        #同じかどうかの確認
        return self.find(x) == self.find(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
            self.size[y] += self.size[x]
            self.size[x] = 0
            self.group[y] = self.group[x] | self.group[y]

        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            self.group[x] = self.group[x] | self.group[y]

        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            self.group[x] = self.group[x] | self.group[y]

    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
u = UnionFind(n+1)
ans_li = [-1 for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    ans_li[a] -= 1
    ans_li[b] -= 1
for i in range(k):
    a,b = map(int, input().split())
    p = u.find(a)
    s = u.group[p]
    if b in s:
        ans_li[a] -= 1
        ans_li[b] -= 1
for i in range(1,n+1):
    p = u.find(i)
    ans_li[i] += len(u.group[p])
    print(ans_li[i], end = " ")

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
frnd=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  frnd[a-1][b-1]=1
  frnd[b-1][a-1]=1
for i in range(k):
  a,b=map(int,input().split())
  frnd[a-1][b-1]=-1
  frnd[b-1][a-1]=-1

flag=[0 for _ in range(n)]
que=[]
grp=[]
gr=[]
g=0
for i in range(n):
  if flag[i]==1:
    continue
  l=frnd[i]
  flag[i]=1
  grp.append(gr)
  gr=[i]
  for j in range(n):
    if l[j]==1 and flag[j]==0:
      que.append(j)
  while len(que)>0:
    m=que.pop()
    gr.append(m)
    l=frnd[m]
    flag[m]=1
    for j in range(n):
      if l[j]==1 and flag[j]==0:
        que.append(j)
grp.append(gr)    
grp=grp[1:]
gr=grp[-1]
gr=list(set(gr))
grp[-1]=gr

ans=[-1 for _ in range(n)]
lgrp=len(grp)
for i in range(n):
  for j in range(lgrp):
    if i in grp[j]:
      k=j
      break
  l=frnd[i]
  for j in grp[k]:
    if l[j]==0:
      ans[i]+=1






print(*ans)

Submission status: Time Limit Exceeded

Solution code:
d = input().split(" ")
n = int(d[0])
m = int(d[1])
k = int(d[2])
ff = [[i] for i in range(n+1)] 
nf = [[i] for i in range(n+1)] 
for i in range(m):
	d = input().split(" ")
	a = int(d[0])
	b = int(d[1])
	for j in ff[a]:
		if b not in ff[j]:
			ff[j] = list(set(ff[j] + ff[b]))
	for j in ff[b]:
		if a not in ff[j]:
			ff[j] = list(set(ff[j] + ff[a]))
	nf[a].append(b)
	nf[b].append(a)
for i in range(k):
	d = input().split(" ")
	a = int(d[0])
	b = int(d[1])
	nf[a].append(b)
	nf[b].append(a)
for i in range(1, n+1):
	l = set(ff[i]) - set(nf[i])
	print(len(l), end = " ")
print()