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: Runtime Error

Solution code:
N,M,K = map(int,input().split())

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

# 木の根を求める
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)

# xとyの属する集合を併合
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]

for a,b in AB:
    unite(a,b)

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

member = [0 for i in range(N+1)]

for p in par:
    member[p] += 1

ans = [member[par[i]]-1 for i in range(N+1)]

for i in range(M):
    a,b = AB[i]
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1
for i in range(K):
    c,d = CD[i]
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1
print(' '.join(map(str,ans[1:])))

Submission status: Runtime Error

Solution code:
N,M,K = map(int,input().split())

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

# 木の根を求める
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

# xとyが同じ集合に属するか否か
def bool_same(x,y):
    return root(x) == root(y)

# xとyの属する集合を併合
def unite(x,y):
    x = root(x)
    y = root(y)
    if x != y:
        par[x] = y

AB = [list(map(int,input().split())) for i in range(M)]
CD = [list(map(int,input().split())) for i in range(K)]

for a,b in AB:
    unite(a,b)

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

member = [0 for i in range(N+1)]

for p in par:
    member[p] += 1

ans = [member[par[i]]-1 for i in range(N+1)]

for a,b in AB:
    if bool_same(a,b):
        ans[a] -= 1
        ans[b] -= 1
for c,d in CD:
    if bool_same(c,d):
        ans[c] -= 1
        ans[d] -= 1
print(' '.join(map(str,ans[1:])))

Submission status: Runtime Error

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

    friendlist = dict()
    for i in range(m):
        tmp = list(map(int, input().split()))
        uf.union(tmp[0]-1, tmp[1]-1)
        if tmp[0] - 1 not in friendlist:
            friendlist[tmp[0]-1] = [tmp[1]-1]
        else:
            friendlist[tmp[0]-1].append(tmp[1]-1)
        if tmp[1] - 1 not in friendlist:
            friendlist[tmp[1]-1] = [tmp[0]-1]
        else:
            friendlist[tmp[1]-1].append(tmp[0]-1)

    blocklist = dict()
    for i in range(k):
        tmp = list(map(int, input().split()))
        if tmp[0] - 1 not in blocklist:
            blocklist[tmp[0]-1] = [tmp[1]-1]
        else:
            blocklist[tmp[0]-1].append(tmp[1]-1)
        if tmp[1] - 1 not in blocklist:
            blocklist[tmp[1]-1] = [tmp[0]-1]
        else:
            blocklist[tmp[1]-1].append(tmp[0]-1)

    for i in range(n):
        blocknum = 0
        if i in blocklist:
            for ii in blocklist[i]:
                if uf.find(ii) == uf.find(i):
                    blocknum += 1
        if i in friendlist:
            friendnum = len(friendlist[i])

        print(str(uf.size(i) - friendnum - blocknum - 1))

Submission status: Runtime Error

Solution code:
from collections import deque
q = deque([])

def get_root(i):
    while True:
        if parent[i] == -1:
            return i
        i = parent[i]

def bfs(i):
    global l
    c = 0
    q.append(i)
    while True:
        if len(q) == 0:
            break
        p = q.popleft()
        l.append(p)
        c += 1
        if not children[p] == -1:
            for j in children[p]:
                q.append(j)
    return c

n, m, k = map(int, input().split())
parent = [-1] * n
children = [-1] * n
d = [0] * n
root = []
rank = []
friend = ["a"] * n
block = ["a"] * n
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if friend[x] == "a":
        friend[x] = [y]
    else:
        friend[x].append(y)
    if friend[y] == "a":
        friend[y] = [x]
    else:
        friend[y].append(x)
    if d[x] == d[y] == 0:
        root.append(x)
        rank.append(1)
        children[x] = [y]
        parent[y] = x
        d[x] = 1
        d[y] = 1
    elif d[x] == 1 and d[y] == 0:
        r = get_root(x)
        children[r].append(y)
        parent[y] = r
        d[y] = 1
    elif d[x] == 0 and d[y] == 1:
        r = get_root(y)
        children[r].append(x)
        parent[x] = r
        d[x] = 1
    else:
        s = get_root(x)
        t = get_root(y)
        if not s == t:
            i = rank[root.index(s)]
            j = rank[root.index(t)]
            if i >= j:
                parent[t] = s
                children[s].append(t)
                if i == j:
                    rank[root.index(s)] += 1
            else:
                parent[s] = t
                children[t].append(s)
for _ in range(k):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if block[x] == "a":
        block[x] = [y]
    else:
        block[x].append(y)
    if block[y] == "a":
        block[y] = [x]
    else:
        block[y].append(x)

c = [0] * len(root)
ans = []
for i in range(n):
    r = get_root(i)
    if c[root.index(r)] == 0:
        l = []
        bfs(r)
        c[root.index(r)] = l
    a = len(c[root.index(r)])
    if friend[i] != "a":
        for j in friend[i]:
            if j in c[root.index(r)]:
                a -= 1
    if block[i] != "a":
        for j in block[i]:
            if j in c[root.index(r)]:
                a -= 1
    ans.append(a - 1)
print(" ".join(map(str, ans)))

Submission status: Runtime Error

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = x, y
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
root = {}

for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
    uf.unite(a - 1, b - 1)

roots = uf.roots()
for r in roots:
    size = uf.size(r)
    root[r] = size - 1

for i in range(K):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1].append(d - 1)
        blocks[d - 1].append(c - 1)

ans = []
for i in range(N):
    ans.append(root[uf.find(i)] - len(blocks[i]) - len(friends[i]))
print(*ans)

Submission status: Runtime Error

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = x, y
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
friends = [[] for _ in range(N)]
blocks = [[] for _ in range(N)]
root = {}

for i in range(M):
    a, b = map(int, input().split())
    friends[a - 1].append(b - 1)
    friends[b - 1].append(a - 1)
    uf.unite(a, b)

roots = uf.roots()
for r in roots:
    size = uf.size(r)
    root[r] = size - 1

for i in range(K):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1].append(d - 1)
        blocks[d - 1].append(c - 1)

ans = []
for i in range(N):
    ans.append(root[uf.find(i)] - len(blocks[i]) - len(friends[i]))
print(*ans)

Submission status: Runtime Error

Solution code:
n, m, k = map(int,input().split())
graph = {
    i : [] for i in range(1, n+1)
}
block = {
    i : [] for i in range(1, n+1)
}
# n=3
# {1: [], 2: [], 3: []}
# print(type(graph[1]))
# >>> list
for i in range(m):
    j, p = map(int, input().split())
    graph[j].append(p)
    graph[p].append(j)
for l in range(k):
    j, p = map(int, input().split())
    block[j].append(p)
    block[p].append(j)
# print(graph)
# print(block)

def search(graph, start, end, marked):
    marked[start] = True
    if start == end:
        return "exist"
    else:
        for target in graph[start]:
            if target == end:
                return "exist"
        for target in graph[start]:
            if target not in marked:
                if  search(graph, target, end, marked)  ==  "exist":
                    return "exist"
                else:
                    pass


# "exist" or "None"

def friendsuggestion(graph, block, whose):
    count = 0
    for i in range(1, n+1):
        if i != whose:
            if search(graph, whose, i, {}) == "exist":
                if i not in graph[whose]:
                    if i not  in block[whose]:
                        print(i)
                        count += 1
    return count

answerlist = [
    friendsuggestion(graph, block, i) for i in range(1, n+1)
]
answer = " ".join(map(str, answerlist))
print(answer)

# print(graph)
# print(block)
# print(friendsuggestion(graph, block, 4))

Submission status: Runtime Error

Solution code:
# input
N, M, K = map(int, input().split())

Frends = [[] for _ in range(N)]
Fs = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Frends[a].append(b)
    Frends[b].append(a)
    if a < b:
        Fs[a].append[b]
    else:
        Fs[b].append[a]

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

# process
# 友人グループを作成
fg = []
for i in range (N):
    l = Fs[i] 
    if len(l) == 0:
        continue

    l.append(i)
    s = set(l)

    t = -1
    j = 0
    fglen = len(fg)
    while j < fglen:
        sfg = s&fg[j]
        if len(sfg) > 0:
            if t < 0:
                t = j
                fg[j] |= s
            else:
                fg[t] |= fg[j]
                fg.pop(j)
                fglen -= 1
        j += 1

    if t < 0:
        fg.append(s)

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for g in fg:
    for f in g:
        cand[f] = len(g)-len(Frends[f])-len(set(Blocked[f])&g)-1

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

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
friend=[list(map(int,input().split())) for i in range(M)]
block=[list(map(int,input().split())) for i in range(K)]
newfriend=[]
def did(M):
    
    did=0
    for i in range(M):
       newfriend[i].sort()
    for i in range(1,M):
        did=0
        q,w=-1,-1
        for k in range(len(fchain)):
           if friend[i][0] in fchain[k]:
                q=k
           if friend[i][1] in fchain[k]:
                w=k
        for j in range(len(fchain)):
            if q!=w and q>=0 and w>=0:
                b=fchain.pop(max(q,w))
                fchain[min(q,w)]+=b
                did=1
                break
            elif (friend[i][0] in fchain[j]) and (friend[i][1] not in fchain[j]):
                fchain[j].append(friend[i][1])
                did=1
                break
            elif (friend[i][0] not in fchain[j]) and (friend[i][1] in fchain[j]):
                fchain[j].append(friend[i][0])
                did=1
                break
            elif (friend[i][0]  in fchain[j]) and (friend[i][1] in fchain[j]):
                did=1
                break
        if did==0:
            fchain.append(friend[i])

if M!=0 and K!=0:
    for i in range(K):
        block[i].sort()
    for i in range(M):
        newdata=friend[i].copy()
        newfriend.append(newdata)
    fchain=[friend[0]]
    did(M)
    ans=[]
    for i in range(1,N+1):
        count=0
        for j in range(len(fchain)):
            if i in fchain[j]:
                where=j
                fchain[j].sort()
                break
        for j in range(len(fchain[where])):
            need=[i,fchain[where][j]]
            need.sort()
            if i==fchain[where][j]:
                continue
            elif (need not in newfriend) and (need not in block):
                count+=1
        ans.append(count)
    print(" ".join(map(str,ans)))
elif M==0:
    print("0")
else:#M!=0 K==0
    for i in range(M):
        newdata=friend[i].copy()
        newfriend.append(newdata)
    fchain=[friend[0]]
    did(M)
    ans=[]
    for i in range(1,N+1):
        count=0
        for j in range(len(fchain)):
            if i in fchain[j]:
                where=j
                fchain[j].sort()
                break
        for j in range(len(fchain[where])):
            need=[i,fchain[where][j]]
            need.sort()
            if i==fchain[where][j]:
                continue
            elif (need not in newfriend):
                count+=1
        ans.append(count)
    print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
friend=[list(map(int,input().split())) for i in range(M)]
block=[list(map(int,input().split())) for i in range(K)]
newfriend=[]
for i in range(M):
    newdata=friend[i].copy()
    newfriend.append(newdata)
fchain=[friend[0]]
did=0
for i in range(M):
    newfriend[i].sort()
for i in range(K):
    block[i].sort()
for i in range(1,M):
    did=0
    q,w=-1,-1
    for k in range(len(fchain)):
       if friend[i][0] in fchain[k]:
            q=k
       if friend[i][1] in fchain[k]:
            w=k
    for j in range(len(fchain)):
        if q!=w and q>=0 and w>=0:
            b=fchain.pop(max(q,w))
            fchain[min(q,w)]+=b
            did=1
            break
        elif (friend[i][0] in fchain[j]) and (friend[i][1] not in fchain[j]):
            fchain[j].append(friend[i][1])
            did=1
            break
        elif (friend[i][0] not in fchain[j]) and (friend[i][1] in fchain[j]):
            fchain[j].append(friend[i][0])
            did=1
            break
        elif (friend[i][0]  in fchain[j]) and (friend[i][1] in fchain[j]):
            did=1
            break
    if did==0:
        fchain.append(friend[i])
ans=[]
for i in range(1,N+1):
    count=0
    for j in range(len(fchain)):
        if i in fchain[j]:
            where=j
            fchain[j].sort()
            break
    for j in range(len(fchain[where])):
        need=[i,fchain[where][j]]
        need.sort()
        if i==fchain[where][j]:
            continue
        elif (need not in newfriend) and (need not in block):
            count+=1
    ans.append(count)
print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
from collections import Counter
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, K = map(int, input().split())
exc = [set() for _ in range(N)]
edge = []

for _ in range(M):
    a, b = map(int, input().split())
    exc[a - 1].add(b - 1)
    exc[b - 1].add(a - 1)
    edge.append((a - 1, b - 1))

edge = np.array(edge).T
matr = csr_matrix(([1 for _ in range(M)], edge), (N, N))
_, labels = connected_components(matr)
ct = Counter(labels)

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

ans = [ct[labels[i]] - len(exc[i]) - 1 for i in range(N)]
print(*ans)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
friend=[list(map(int,input().split())) for i in range(M)]
block=[list(map(int,input().split())) for i in range(K)]
newfriend=[]
for i in range(M):
    newdata=friend[i].copy()
    newfriend.append(newdata)
fchain=[friend[0]]
did=0
for i in range(M):
    newfriend[i].sort()
for i in range(K):
    block[i].sort()
for i in range(1,M):
    did=0
    for j in range(len(fchain)):
        q,w=-1,-1
        for k in range(len(fchain)):
            if friend[i][0] in fchain[k]:
                q=k
            if friend[i][1] in fchain[k]:
                w=k
        if q!=w and q>=0 and w>=0:
            b=fchain.pop(max(q,w))
            fchain[min(q,w)]+=b
            did=1
            break
        elif (friend[i][0] in fchain[j]) and (friend[i][1] not in fchain[j]):
            fchain[j].append(friend[i][1])
            did=1
            break
        elif (friend[i][0] not in fchain[j]) and (friend[i][1] in fchain[j]):
            fchain[j].append(friend[i][0])
            did=1
            break
        elif (friend[i][0]  in fchain[j]) and (friend[i][1] in fchain[j]):
            did=1
            break
    if did==0:
        fchain.append(friend[i])
ans=[]
for i in range(1,N+1):
    count=0
    for j in range(len(fchain)):
        if i in fchain[j]:
            where=j
            fchain[j].sort()
            break
    for j in range(len(fchain[where])):
        need=[i,fchain[where][j]]
        need.sort()
        if i==fchain[where][j]:
            continue
        elif (need not in newfriend) and (need not in block):
            count+=1
    ans.append(count)
print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
N, M, K = list(map(int, input().split()))
AB_list = []
for _ in range(M):
    A, B = sorted(list(map(int, input().split())))
    AB_list.append([A - 1, B - 1])
CD_list = []
for _ in range(K):
    C, D = sorted(list(map(int, input().split())))
    CD_list.append([C - 1, D - 1])

parents = [i for i in range(N)]

def root(x):
    if parents[x] == x:
        return x
    parents[x] = root(parents[x])
    return parents[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        parents[rx] = ry

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

for A, B in AB_list:
    unite(A, B)
for i in range(N):
    root(i)

answers = [0] * N
for i in range(N):
    may_friends = parents.count(root(i)) - 1
    friends = sum(1 for x, y in AB_list if x == i or y == i)
    blocks = sum(1 for x, y in CD_list if (x == i or y == i) and root(x) == root(y))
    answers[i] = may_friends - friends - blocks

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

Submission status: Runtime Error

Solution code:
N, M, K = list(map(int, input().split()))
AB_list = []
for _ in range(M):
    A, B = sorted(list(map(int, input().split())))
    AB_list.append([A - 1, B - 1])
CD_list = []
for _ in range(K):
    C, D = sorted(list(map(int, input().split())))
    CD_list.append([C - 1, D - 1])

parents = [i for i in range(N)]

def root(x):
    if parents[x] == x:
        return x
    parents[x] = root(parents[x])
    return parents[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        parents[rx] = ry

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

for A, B in AB_list:
    unite(A, B)

answers = [0] * N
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        pair = sorted([i, j])
        if pair in AB_list:
            continue
        if pair in CD_list:
            continue
        if root(i) != root(j):
            continue
        answers[i] += 1

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

Submission status: Runtime Error

Solution code:
class UnionFind():
  def __init__(self, size):
    self.par = [i for i in range(size+1)]
    self.size = [1 for i in range(size+1)]
  
  def root(self, node):
    if self.par[node] == node:
      return self.node
    else:
      return self.root(self.par[node])
    
  def same(self, node1, node2):
    if self.root(node1) == self.root(node2):
      return True
    else:
      return False
    
  def size(self, node):
    return self.size[self.root(node)]
    
  def merge(self, node1, node2):
    if not self.same(node1, node2):
      self.size[self.root(node1)] += self.size[self.root(node2)]
      self.par[node2] = self.par[node1]
      
  def isRoot(self, node):
    if self.par[node] = node:
      return True
    else:
      return False
    
n, m, k = map(int, input().split())
uf = UnionFind(n)
outs = [0 for _ in range(n+1)]
for i in range(m):
  a, b = map(int, input().split())
  uf.merge(a, b)
  outs[a] += 1
  outs[b] += 1
for i in range(k):
  c, d = map(int, input().split())
  outs[c] += 1
  outs[d] += 1
  
ans = []
for i in range(1, n+1):
  ans.append(uf.size(i) - outs[i])
  
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

#再帰関数は非常にダメダメですねぇ

N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]
sys.setrecursionlimit(2*N)
#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = []
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]

def dfs(i):
    #if i not in bgraph[j]:
    #    seen[i]= True
    #else:
    #    seen[i]="block"
    #if graph[i]:
    #    for nec in graph[i]:
    #        if seen[nec] == False:
    #            dfs(nec,j)
    seen[i] = True
    que = deque([i])
    while que:

        neci = que.pop()
        for nec in graph[neci]:
            if seen[nec]== False:
                if nec not in bgraph[i]:
                    seen[nec]=True
                else:
                    seen[nec]="block"
                que.append(nec)

for i_n in range(N):
    seen = [False for _ in range(N)]
    dfs(i_n)
    #print(seen)
    cnt.append(seen.count(True) - 1 - len(graph[i_n]))

print(*cnt)

Submission status: Runtime Error

Solution code:
N, M, K = map(int, input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]

#print(friend)
#print(block)
graph = [[] for _ in range(N)]
bgraph = [[] for _ in range(N)]
cnt = []
for i in range(M):
    ii, jj = friend[i]
    graph[ii-1].append(jj-1)
    graph[jj-1].append(ii-1)

for i in range(K):
    ii, jj = block[i]
    bgraph[ii-1].append(jj-1)
    bgraph[jj-1].append(ii-1)

#print(graph)
#print(bgraph)

seen = [False for _ in range(N)]

def dfs(i,j):
    if i not in bgraph[j]:
        seen[i]= True
    else:
        seen[i]="block"
    if graph[i]:
        for nec in graph[i]:
            if seen[nec] == False:
                dfs(nec,j)


for i_n in range(N):
    seen = [False for _ in range(N)]
    dfs(i_n,i_n)
    cnt.append(seen.count(True) - 1 - len(graph[i_n]))

print(*cnt)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        friends_chain.unite(a, b)
        friend_or_block[a] += 1
        friend_or_block[b] += 1

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

    print(*[friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])

    class UnionFindTree:
        def __init__(self, n):
            self.parent = [-1] * n

        def root(self, x):
            p, s = self.parent[x], list()
            while p >= 0:
                s.append(x)
                x, p = p, self.parent[p]
            for c in s: self.parent[c] = x
            return x

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

        def count(self, x): return -self.parent[self.root(x)]

        def unite(self, x, y):
            xr, yr = self.root(x), self.root(y)
            if xr == yr: return
            if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
            self.parent[xr] += self.parent[yr]
            self.parent[yr] = xr

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from numpy import array, zeros, sort, hstack, diag, argsort
from numpy.linalg import eig
N, M, K = [int(i) for i in input().split()]
Rel = zeros([N, N], int)
F = array([[int(i) for i in input().split()] for _ in range(M)])
B = array([[int(i) for i in input().split()] for _ in range(K)])
F = (sort(F)-1).T
F = list(hstack([F, F[::-1]]))
B = (sort(B)-1).T
B = list(hstack([B, B[::-1]]))
Rel[F] = 1
Rel += diag(2*N*array(list(range(N))))
eigval, eigvec = eig(Rel)
eig_ = (eigvec!=0).T
eig_ = eig_[argsort(eigval)]
eig_[F] = 0
eig_[B] = 0
K = sum(eig_, 0) - 1
[print(k) for k in K]

Submission status: Runtime Error

Solution code:
from numpy import array
from numpy.linalg import eig
from numpy import zeros
from numpy import sort
from numpy import hstack
N, M, K = [int(i) for i in input().split()]
Rel = zeros([N, N], int)
F = array([[int(i) for i in input().split()] for _ in range(M)])
B = array([[int(i) for i in input().split()] for _ in range(K)])
F = (sort(F)-1).T
F = list(hstack([F, F[::-1]]))
B = (sort(B)-1).T
B = list(hstack([B, B[::-1]]))
Rel[F] = 1
eigval, eigvec = eig(Rel)
eig_ = (eigvec!=0)
eig_[F] = 0
eig_[B] = 0
K = sum(eig_, 0) - 1
[print(k) for k in K]

Submission status: Runtime Error

Solution code:
from numpy import array
from numpy.linalg import eig
from numpy import zeros
from numpy import sort
from numpy import hstack
N, M, K = [int(i) for i in input().split()]
Rel = zeros([N, N], int)
F = array([[int(i) for i in input().split()] for _ in range(M)])
B = array([[int(i) for i in input().split()] for _ in range(K)])
t = time.time()
F = (sort(F)-1).T
F = list(hstack([F, F[::-1]]))
B = (sort(B)-1).T
B = list(hstack([B, B[::-1]]))
Rel[F] = 1
eigval, eigvec = eig(Rel)
eig_ = (eigvec!=0)
eig_[F] = 0
eig_[B] = 0
K = sum(eig_, 0) - 1
[print(k) for k in K]

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc157/submissions/10475457

import sys
readline = sys.stdin.readine

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)

seen = [-1] * (N + 1)
group = 0


def dfs(graph, s):
    stack = [s]
    seen[s] = group
    n_connection = 1

    while stack:
        u = stack.pop()
        for v in graph[u]:
            if seen[v] == -1:
                n_connection += 1
                seen[v] = group
                stack.append(v)

    return n_connection


union = {}
for i in range(1, N + 1):
    if seen[i] == -1:
        n = dfs(F, i)
        union[group] = n
        group += 1

ans = []
for i in range(1, N + 1):
    tmp = 0
    tmp += union[seen[i]] - 1
    tmp -= len(F[i])
    for j in B[i]:
        if seen[j] == seen[i]:
            tmp -= 1
    ans.append(tmp)

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