I am not able to figure out this question, is this a graphs question or dp questions?
Also I am not able to figure out how take input in c++.
I have written a small snipett in python
# def getParent(dsu,child):
# while child != dsu[child]:
# child = dsu[child]
# return child
def findLongestPath(graph,start,childDp,dp,n,dsu):
if start in dp:
return dp[start]
ans = 0
if start in graph:
for i in graph[start]:
subAns = findLongestPath(graph,i,childDp,dp,n,dsu) + 1
if subAns > ans:
ans = subAns
childDp[start] = i
# parents = set([getParent(dsu,start)])
# for i in range(n):
# currentParent = getParent(dsu,i)
# if currentParent not in parents:
# subAns = findLongestPath(graph,i,childDp,dp,n,dsu) + 1
dp[start] = ans
return ans
try:
while True:
n = int(input())
wines = {}
wineNames = []
dsu = [i for i in range(n)]
for i in range(n):
wine = input()
wines[wine] = i
wineNames.append(wine)
m = int(input())
graph = {}
# g = {}
for i in range(m):
wine = input().split(" ")
a,b = wines[wine[0]],wines[wine[1]]
# dsu[getParent(dsu,a)] = dsu[getParent(dsu,b)]
if a not in graph:
graph[a] = []
graph[a].append(b)
start = wines[wineNames[0]]
childDp = {}
dp = {}
print("Graph is ",graph)
findLongestPath(graph,start,childDp,dp,n,dsu)
while start != childDp[start]:
print(wineNames[start],end = " ")
start = childDp[start]
print(wineNames[start],end = " ")
print()
print("Done")
input()
except:
print("end of line detected")