n개의 색상이 지정된 노드와 m개의 서로 다른 모서리가 있는 방향 그래프가 있다고 가정합니다. 그리고 노드는 0에서 n-1까지 번호가 매겨집니다. 소문자로 된 문자열 col이 있습니다. 여기서 col[i]는 이 그래프(0-인덱스)에서 i번째 노드의 색상을 나타냅니다. edge[j] =(u, v)가 나타내는 에지 목록도 있으며 u와 v 사이에 에지가 있습니다.
그래프의 유효한 경로는 xi에서 xi+1까지의 방향 간선이 있도록 1에서 k까지의 모든 i에 대한 노드 xi의 시퀀스입니다. 경로의 색상은 해당 경로의 가장 빈번한 노드 색상입니다. 해당 그래프에서 유효한 경로의 가장 큰 색상 값을 찾아야 합니다. 그래프에 주기가 있으면 -1을 반환합니다.
따라서 입력이 col ="aabada" edge =[(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)와 같은 경우 ],
그러면 출력은 0 -> 1 -> 2 -> 3 -> 5가 'a' 색상의 가장 긴 경로를 가지므로 4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n:=열 크기
-
graph:=edge list에서 주어진 그래프
-
indegree:=노드와 해당 차수 값을 포함하는 맵
-
대기열:=새 목록
-
dp:=n x 26 크기의 배열을 만들고 0으로 채움
-
colorvalues:=col의 모든 c에 대해 알파벳 c의 순서로 목록을 만듭니다.
-
범위 0에서 n - 1에 있는 u에 대해 수행
-
u가 indegree가 아니면
-
큐 끝에 u 삽입
-
dp[u, 색상값[u]]:=1
-
-
-
방문:=0
-
대기열이 비어 있지 않은 동안 수행
-
u:=대기열의 앞 요소 및 이후 삭제
-
방문 :=방문 + 1
-
그래프[u]의 각 v에 대해 수행
-
0에서 25 사이의 c에 대해 수행
-
dp[v, c] =dp[v, c]의 최대값 및 (dp[u, c] + (c가 colorvalues[v]와 같으면 1, 그렇지 않으면 0)
-
-
차수[v] :=차수[v] - 1
-
indegree[v]가 0과 같으면
-
큐 끝에 v 삽입
-
델 정도[v]
-
-
-
-
-
반환 -1
-
-
dp의 최대 요소를 반환
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
from collections import defaultdict
def solve(col, edges):
n=len(col)
graph=defaultdict(list)
indegree=defaultdict(int)
for u,v in edges:
graph[u].append(v)
indegree[v]+=1
queue=[]
dp=[[0]*26 for _ in range(n)]
colorvalues=[ord(c)-ord("a") for c in col]
for u in range(n):
if u not in indegree:
queue.append(u)
dp[u][colorvalues[u]]=1
visited=0
while queue:
u=queue.pop()
visited+=1
for v in graph[u]:
for c in range(26):
dp[v][c]=max(dp[v][c],dp[u][c] + (c==colorvalues[v]))
indegree[v]-=1
if indegree[v]==0:
queue.append(v)
del indegree[v]
if visited<n:
return -1
return max(max(x) for x in dp)
col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
print(solve(col, edges)) 입력
"aabada", [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
출력
4