ABC 157 D - Lösungsvorschläge für Freunde in Python!

Das jüngste D-Problem ist aufgrund seiner Knochen oft unlösbar, und ich bin heutzutage traurig. Ich habe mich gefragt, wie ich es lösen soll, auch wenn es vorbei ist, also habe ich mein Bestes versucht, es zu lösen.

Das Schlüsselwort lautet diesmal __ "ungerichteter Graph" __ "verkettete Komponente" __. Die Punkte sind __ "DFS" __ und __ "set" __!

Link zum Problem ABC 157 D - Freundliche Vorschläge

Antworten während des Wettbewerbs

Ich bemerkte, dass es sich um ein ungerichtetes Diagramm handelte und entschied mich sofort, es mit DFS zu lösen. Verwenden Sie von jedem Scheitelpunkt aus DFS, um Punkte zu zählen, die weder Freunde noch Blöcke der verbundenen Komponenten sind. Ich dachte, es wäre nicht rechtzeitig für die Doppelschleife, aber es war TLE. Dies ist die Zeit während des Wettbewerbs.

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)

Antworten nach dem Wettbewerb

Bei der Verwendung von in habe ich gehört, dass Set schneller als List ist, daher habe ich mich für die Verwendung entschieden. Als Ergebnis des Kampfes gegen TLE durch verschiedene Versuche und Irrtümer erhielt ich unten AC.

Sammeln Sie die Verknüpfungskomponenten in der Verknüpfung und suchen Sie die Verknüpfungskomponenten. Nach der Suche nach der Verknüpfungskomponente Sie wird berechnet, indem die Anzahl der Freund- und Blockbeziehungen subtrahiert wird, die für jeden Punkt der Verbindungskomponente gezeichnet werden sollen.

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

Einfallsreichtum

Da es offensichtlich nutzlos ist, die Suche zu überprüfen, habe ich hinzugefügt, die Suche nicht zu suchen.

if visited[i]:
    continue

Ich habe überprüft, ob alle Eckpunkte für einen bestimmten Punkt Freunde waren. Ich habe mich geändert, um nur nach denen zu suchen, die mit diesem Punkt befreundet sind.

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

Ich habe eine Möglichkeit entwickelt, die Anzahl der Freundschaften oder Blockbeziehungen von der Größe der Verknüpfungskomponente zu subtrahieren.

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

Mit anderen Worten, was bedeutet das ... Unter Verwendung des Produktsatzes wird die Anzahl der Freund- und Blockbeziehungen aus den verbundenen Komponenten berechnet.

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

#Verbindungskomponente
link = {1,2,4,9,10}
#1 und 4/10 sind Freunde
f[1] = {4,10}
#1 blockiert 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