Problem: 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?

Submission attempts (in order):
# 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)))


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

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Frends[a].append(b)
    Frends[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):
    fs = Frends[i]
    for f in fs:
        if i > f:
            break

        t = -1
        s = set([i, f])
        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            sand = s&g
            if t < 0:
                if len(sand) > 0:
                    t = j
                    if sand == s:
                        break
                    elif i in sand:
                        g.add(f)
                    else:
                        g.add(i)

            elif len(sand) > 0:
                
                fg[t] = fg[t] | g
                fg.pop(j)
                fglen -= 1
            
            j += 1

        if t < 0:
            fg.append(s)


cand = [0 for _ in range(N)]
for i in range(N):
    for g in fg:
        if i in g:
            cand[i] = len(g)-len(Frends[i])-len(set(Blocked[i])&g)-1
            break

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


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

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Frends[a].append(b)
    Frends[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 = [x for x in Frends[i] if x>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)))


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

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

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

# process

fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        flg = False
        for g in fg:
            if i in g and f in g:
                flg = True
                continue
            elif not (i in g or f in g):
                continue
            else:
                if i in g:
                    g.add(f)
                else:
                    g.add(i)
                
                flg = True
                break
            
        if not flg:
            fg.append(set([i, f]))

for i in range(len(fg)-1):
    for j in range(i+1, len(fg)):
        if fg[i] & fg[j] != set():
            fg[i] = fg[i] | fg[j]
            fg[j].clear()

#print(fg)


cand = []
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand.append((i, f,))

print(cand)


ans = [0 for _ in range(N)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

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


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

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Frends[a].append(b)
    Frends[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):
    fs = Frends[i]
    for f in fs:
        if i > f:
            continue

        t = -1
        s = set([i, f])
        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            sand = s&g
            if t < 0:
                if len(sand) > 0:
                    t = j
                    if sand == s:
                        break
                    elif i in sand:
                        g.add(f)
                    else:
                        g.add(i)

            elif len(sand) > 0:
                
                fg[t] = fg[t] | g
                fg.pop(j)
                fglen -= 1
            
            j += 1

        if t < 0:
            fg.append(s)


cand = [0 for _ in range(N)]
for i in range(N):
    for g in fg:
        if i in g:
            cand[i] = len(g)-len(Frends[i])-len(set(Blocked[i])&g)-1
            break

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


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

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

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

# process

checked = set()
ans = [0]*N

for i in range (N):
    if i in checked:
        continue
    
    fg = set()

    stack = list(Friends[i])
    while stack:
        f = stack.pop()
        if f in checked:
            continue

        checked.add(f)
        fg.add(f)
        stack.extend(Friends[f])

    for f in fg:
        ans[f] += len(fg)-1-len(fg&(Friends[f]|Blocked[f]))

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


Verdicts: Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted