ABC 157 D - Résolvez les suggestions d'amis en Python!

Le problème D récent est souvent insoluble à cause de ses os, et je me sens triste aujourd'hui. Je me demandais comment le résoudre même après la fin, alors j'ai fait de mon mieux pour le résoudre.

Le mot clé cette fois est __ "graphe non orienté" __ "composant concaténé" __. Les points sont __ "DFS" __ et __ "set" __!

Lien vers le problème ABC 157 D - Suggestions d'amis

Réponses pendant le concours

J'ai remarqué qu'il s'agissait d'un graphe non orienté et j'ai immédiatement décidé de le résoudre avec DFS. À partir de chaque sommet, utilisez DFS pour compter les points qui ne sont ni des amis ni des blocs des composants connectés. Je pensais que ce ne serait pas à temps pour la double boucle, mais c'était TLE. C'est le temps écoulé pendant le concours.

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)]

g = [[False]*(N+1) for _ in range(N+1)]
for i in friend:
    g[i[0]][i[1]] = True
    g[i[1]][i[0]] = True


b = [[False]*(N+1) for _ in range(N+1)]
for i in block:
    b[i[0]][i[1]] = True
    b[i[1]][i[0]] = True
    
stack=deque()
ans = []

for i in range(1,N+1):
    cnt = 0
    visited = [0] * (N+1)
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in range(1,N+1):
            if g[n][j] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                if g[i][j] == False and b[i][j]==False:
                    cnt+=1
    ans.append(cnt)
print(*ans)

Réponses après le concours

Lors de l'utilisation dans, j'ai entendu dire que Set est plus rapide que List, j'ai donc décidé de l'utiliser. À la suite de la lutte contre TLE à travers divers essais et erreurs, j'ai reçu AC ci-dessous.

Accumulez les composants de liaison dans le lien et recherchez les composants de liaison. Après avoir recherché le composant de liaison, Il est calculé en soustrayant le nombre de relations d'amis et de relations de bloc à dessiner pour chaque point du composant de connexion.

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)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

Point d'ingéniosité

Comme il est évidemment inutile de vérifier recherché, j'ai ajouté de ne pas rechercher recherché.

if visited[i]:
    continue

Je vérifiais si tous les sommets étaient amis pour un certain point, J'ai changé pour rechercher uniquement ceux qui ont une amitié avec ce point.

for j in range(1,N+1):
# ↓↓↓
for j in f[n]:

J'ai conçu un moyen de soustraire le nombre d'amitiés ou de bloquer les relations de la taille du composant de liaison.

ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1

En d'autres termes, qu'est-ce que cela signifie ... En utilisant l'ensemble de produits, le nombre de relations d'ami et de relations de bloc est calculé à partir des composants connectés.

f = [set for _ in range(10)]
b = [set for _ in range(10)]

#Composant de liaison
link = {1,2,4,9,10}
#1 et 4/10 sont amis
f[1] = {4,10}
#1 bloque le 5/6/9
b[1] = {5,6,9}

print(link&f[1], link&b[1])
print(len(link&f[1]), len(link&b[1]))

{10, 4} {9}
2 1