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 numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]


def dfs(now):
    if know[now]: return
    know[now] = 1
    for next in f[now]: dfs(next)

n,m,k = imap()
f = adj(n+1)
for i in range(m):
    a,b = imap()
    f[a].append(b)
    f[b].append(a)
ng = adj(n+1)
for i in range(k):
    c,d = imap()
    ng[c].append(d)
    ng[d].append(c)

anss = []
for i in range(1,n+1):
    know = iarr(n+1)
    ok = iarr(n+1)
    dfs(i)
    ans = sum(know) -1 #自分自身を除く
    for elm in f[i]:
        if know[elm]: ans -= 1
    for elm in ng[i]:
        if know[elm]: ans -= 1
    anss.append(ans)
print(*anss)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())

friend = [set([]) for i in range(n)]
block = [0] * 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())

uf = UnionFind(n)
ab = [list(map(int, input().split())) for i in range(m)]
for a, b in ab:
    uf.union(a-1, b-1)
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)

groups = [set(uf.members(i)) for i in range(n)]

for i in range(k):
    c, d = map(int, input().split())
    if uf.same(d-1, c-1):
        block[c-1]+=1
        block[d-1]+=1

ans = []
for i in range(n):
    ans.append(len(groups[i]) - len(friend[i]) - block[i] -1 )
print(' '.join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())

friend = [set([]) for i in range(n)]
block = [0] * 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())

uf = UnionFind(n)
ab = [list(map(int, input().split())) for i in range(m)]
for a, b in ab:
    uf.union(a-1, b-1)
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)

groups = [set(uf.members(i)) for i in range(n)]

for i in range(k):
    c, d = map(int, input().split())
    if d-1 in groups[c-1]:
        block[c-1]+=1
        block[d-1]+=1

ans = []
for i in range(n):
    ans.append(len(groups[i]) - len(friend[i]) - block[i] -1 )
print(' '.join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())

friend = [set([]) 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())

uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)

for i in range(k):
    c, d = map(int, input().split())
    friend[c-1].add(d-1)
    friend[d-1].add(c-1)

ans = []
for i in range(n):
    ans.append(len(set(uf.members(i)) - friend[i])-1)
print(' '.join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())

block = [[] for i in range(n)]
friend = [[] 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())

uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

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

ans = []
for i in range(n):
    ans.append(len(set(uf.members(i)) - (set(friend[i])|set(block[i])))-1)
print(' '.join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
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)]

block = [[] for i in range(n)]
friend = [[] 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())


uf = UnionFind(n)
for a, b in ab:
    uf.union(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

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

for i in range(n):
    ans = len(set(uf.members(i)) - (set(friend[i])|set(block[i])))-1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]


def dfs(now):
    if know[now]: return
    know[now] = 1
    if not now in [i]+f[i]+ng[i]: ok[now] = 1
    for next in f[now]: dfs(next)

n,m,k = imap()
f = adj(n+1)
for i in range(m):
    a,b = imap()
    f[a].append(b)
    f[b].append(a)
ng = adj(n+1)
for i in range(k):
    c,d = imap()
    ng[c].append(d)
    ng[d].append(c)

anss = []
for i in range(1,n+1):
    know = iarr(n+1)
    ok = iarr(n+1)
    dfs(i)
    ans = sum(ok)
    anss.append(ans)
print(*anss)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def same(x, y):
        return find(x) == find(y)
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    par = [-1] * n
    friend = {e: set() for e in range(n)}
    table = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    for i1 in range(n):
        mem = members(i1)
        for meme in mem:
            table[i1][meme] = 1
        table[i1][i1] = 0
        for frie in friend[i1]:
            table[i1][frie] = 0
    m = map(int, read().split())
    cd = zip(m, m)
    for c, d in cd:
        c -= 1
        d -= 1
        table[c][d] = 0
        table[d][c] = 0
    for i1 in range(n):
        r = sum(table[i1])
        print(r, end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def same(x, y):
        return find(x) == find(y)
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    par = [-1] * n
    friend = {e: set() for e in range(n)}
    foe = {e: set() for e in range(n)}
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    m = map(int, read().split())
    cd = zip(m, m)
    for c, d in cd:
        c -= 1
        d -= 1
        foe[c].add(d)
        foe[d].add(c)
    for i1 in range(n):
        r = len(set(members(i1)) - friend[i1] - foe[i1]) - 1
        print(r, end=' ')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Union_Find():
    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())

A=[set() for _ in range(N+1)]
U=Union_Find(N+1)
for _ in range(M):
    a,b=map(int,input().split())
    A[a].add(b)
    A[b].add(a)
    U.union(a,b)

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

T=U.all_group_members()
V={x:set(T[x]) for x in T}

S=[]
for k in range(1,N+1):
    S.append(str(len(V[U.find(k)]-(A[k]|C[k]|{k}))))
print(" ".join(S))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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


uf = UnionFind(n)

friends = [0] * (n + 1)
chain = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.union(a, b)

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if uf.find(i) == uf.find(j):
            chain[i] += 1

for _ in range(k):
    c, d = map(int, input().split())
    if uf.find(c) == uf.find(d):
        friends[c] += 1
        friends[d] += 1

ans = []
for i in range(1, n + 1):
    ans.append(chain[i] - friends[i] - 1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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


uf = UnionFind(n)

friends = defaultdict(int)
chain = defaultdict(int)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a] += 1
    friends[b] += 1
    uf.union(a, b)

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if uf.find(i) == uf.find(j):
            chain[i] += 1

for _ in range(k):
    c, d = map(int, input().split())
    if uf.find(c) == uf.find(d):
        friends[c] += 1
        friends[d] += 1

ans = []
for i in range(1, n + 1):
    ans.append(chain[i] - friends[i] - 1)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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 other_members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root and i != x]

        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 = list(map(int, input().split()))
    uf = UnionFind(n)
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        uf.union(a, b)
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        c, d = list(map(lambda x: int(x) - 1, input().split()))
        blocks[c].add(d)
        blocks[d].add(c)
    print(' '.join([str(len(set(uf.other_members(i)) - friends[i] - blocks[i])) for i in range(n)]))




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
n,m,k=mi()
friend=[[] for _ in range(n+1)]
block=[[] for _ in range(n+1)]
ans=[0]*n
for i in range(m):
  a,b=mi()
  friend[a].append(b)
  friend[b].append(a)
for i in range(k):
  a,b=mi()
  block[a].append(b)
  block[b].append(a)
for i in range(1,n+1):
  q=deque([i])
  visited=[0]*(n+1)
  visited[i]=1
  count=0
  while q:
    s=q.popleft()
    for xx in friend[s]:
      if visited[xx]==0:
        if not xx in block[i]:
          count+=1
        q.append(xx)
        visited[xx]=1
  ans[i-1]=(count-len(friend[i]))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
n,m,k=mi()
friend=[[] for _ in range(n+1)]
block=[[] for _ in range(n+1)]
for i in range(m):
  a,b=mi()
  friend[a].append(b)
  friend[b].append(a)
for i in range(k):
  a,b=mi()
  block[a].append(b)
  block[b].append(a)
for i in range(1,n+1):
  q=deque([i])
  visited=[0]*(n+1)
  visited[i]=1
  count=0
  while q:
    s=q.popleft()
    for xx in friend[s]:
      if visited[xx]==0:
        if not xx in block[i]:
          count+=1
        q.append(xx)
        visited[xx]=1
  print(count-len(friend[i]),end=" ")

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
fr = [[] for i in range(N+1)]
bl = [[] for i in range(N+1)]
for _ in range(M):
    A,B = map(int, input().split())
    fr[A].append(B)
    fr[B].append(A)
for _ in range(K):
    C,D = map(int, input().split())
    bl[C].append(D)
    bl[D].append(C)

leader = [0]*(N+1)
d = {}
for root in range(1,N+1):
    if leader[root]!=0:
        continue
    d[root] = set([root])
    stack = [root]
    while stack:
        start = stack.pop()
        leader[start] = root
        for v in fr[start]:
            if leader[v]!=0:
                continue
            d[root].add(v)
            stack.append(v)

ans = [0]*(N+1)
for i in range(1,N+1):
    cluster = d[leader[i]]
    ans[i] = len(cluster) - len(fr[i]) - 1
    for b in bl[i]:
        if b in cluster:
            ans[i] -= 1
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,m,k= map(int, input().split())
g = [[] for i in range(N)]
h = [[] for i in range(N)]
for _ in range(m):
  a, b = map(int, input().split())
  g[b-1].append(a-1)
  g[a-1].append(b-1)
for _ in range(k):
  a, b = map(int, input().split())
  h[b-1].append(a-1)
  h[a-1].append(b-1)
def bfs(n):
  cnt = 0
  a = [-1]*N
  q=deque()
  q.append(n)
  a[n] = 0
  for i in h[n]:
    a[i] = -2
  while len(q):
    x=q.popleft()
    for i in g[x]:
      if a[i]==-1: 
        a[i]=a[x]+1
        if a[i] >= 2:
          cnt += 1
        q.append(i)
      if a[i]==-2:
        a[i]=a[x]+1
        q.append(i)
  return cnt
ans = []
for i in range(N):
  ans.append(str(bfs(i)))
print(' '.join(ans))

Submission status: Time Limit Exceeded

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

    n, m, k = map(int, input().split())
    f = [[] for i in range(n)]
    BL = [[] for i in range(n)]
    ans = [0] * n
    for _ in range(m):
        a, b = map(int, input().split())
        f[a-1].append(b-1)
        f[b-1].append(a-1)
    for _ in range(k):
        c, d = map(int, input().split())
        BL[c-1].append(d-1)
        BL[d-1].append(c-1)
    D = {}
    parent = [-1] * n
    visited = [False] * n
    for root in range(n):
        if visited[root]:
            continue
        D[root]  = set([root])
        stack = [root]
        while stack:
            x = stack.pop()
            visited[x] = True
            parent[x] = root
            for t in f[x]:
                if visited[t]:
                    continue
                D[root].add(t)
                stack.append(t)
    for i in range(n):
        grp = D[parent[i]]
        tans = len(grp) - len(f[i]) - 1
        for block in BL[i]:
            if block in grp:
                tans -= 1
        ans[i] = tans
    print(*ans)
main()

Submission status: Time Limit Exceeded

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

n, m, k = map(int, input().split())
f = [[] for i in range(n)]
BL = [[] for i in range(n)]
ans = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    f[a-1].append(b-1)
    f[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    BL[c-1].append(d-1)
    BL[d-1].append(c-1)
D = {}
parent = [-1] * n
visited = [False] * n
for root in range(n):
    if visited[root]:
        continue
    D[root]  = set([root])
    stack = [root]
    while stack:
        x = stack.pop()
        visited[x] = True
        parent[x] = root
        for t in f[x]:
            if visited[t]:
                continue
            D[root].add(t)
            stack.append(t)
for i in range(n):
    grp = D[parent[i]]
    tans = len(grp) - len(f[i]) - 1
    for block in BL[i]:
        if block in grp:
            tans -= 1
    ans[i] = tans
print(*ans)

Submission status: Time Limit Exceeded

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

    n, m, k = map(int, input().split())
    f = {i: set() for i in range(1, n+1)}
    BL = {i: set() for i in range(1, n+1)}
    ans = [0] * n
    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())
        BL[c].add(d)
        BL[d].add(c)
    for i in range(1, n+1):
        ff = f[i].copy()
        q = deque(f[i])
        while q:
            t = q.popleft()
            for x in f[t]:
                if x not in ff:
                    ff.add(x)
                    q.append(x)
        ans[i-1] = max(0, len(ff - f[i] - BL[i]) - 1)
    print(*ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

    n, m, k = map(int, input().split())
    f = {i: set() for i in range(1, n+1)}
    BL = {i: set() for i in range(1, n+1)}
    ans = [0] * n
    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())
        BL[c].add(d)
        BL[d].add(c)
    for i in range(1, n+1):
        ff = f[i].copy()
        q = deque(f[i])
        while q:
            t = q.popleft()
            for x in f[t]:
                if x not in ff:
                    ff.add(x)
                    q.append(x)
        ans[i-1] = max(0, len(ff - f[i] - BL[i]) - 1)
    print(*ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m, k = map(int, input().split())
f = {i: set() for i in range(1, n+1)}
BL = {i: set() for i in range(1, n+1)}
ans = [0] * n
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())
    BL[c].add(d)
    BL[d].add(c)
for i in range(1, n+1):
    ff = f[i].copy()
    q = deque(f[i])
    while q:
        t = q.popleft()
        for x in f[t]:
            if x not in ff:
                ff.add(x)
                q.append(x)
    ans[i-1] = max(0, len(ff - f[i] - BL[i]) - 1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

C={i:set() for i in range(1,N+1)}
for _ in range(K):
    c,d=map(int,input().split())
    C[c].add(d)
    C[d].add(c)

T={i:False for i in range(1,N+1)}
def Connected_Component(v):
    S=deque([v])
    T[v]=True
    q=1
    D=[]
    while S:
        w=S.pop()
        D.append(w)
        for u in [u for u in A[w] if not T[u]]:
            q+=1
            T[u]=True
            S.append(u)

    return D

s=0
F=[0]*(N+1)
E=[]
for v in range(1,N+1):
    if not T[v]:
        B=Connected_Component(v)
        E.append(set(B))
        for x in B:
            F[x]=s
        s+=1

P=[]
for i in range(1,N+1):
    c=F[i]
    P.append(str(len(E[c]-(A[i]|C[i]|{i}))))
print(" ".join(P))