Also die Zyklen kann man ja mit Tiefensucher erschlagen.
Dann kannst du ungefähr so vorgehen, dass du dir einen beliebigen Knoten nimmst. Du weist, er ist Teil eines zusammenhängenden nicht-zyklischen Graphen.
Jetzt führst du für diesen Knoten wieder eine Tiefensuche durch, sodass du für jedes Kindelement eine Zahl bekommst, "wie tief es geht" also wie weit man gehen kann. Nimm die beiden maximalen Werte und du hast die länge der längsten Kette für diesen (Teil-)Graphen.
Idealerweise strechst du alle Knoten aus einer Liste heraus, die du auf diesem Weg besucht hast. (Du besuchst ja alle Knoten dieses Teilgraphen)
Jetzt kannst du das gleiche nochmal für den nächsten Knoten in der Liste machen (der noch nicht herausgestrichen ist)
Das sollte die Längste Kette liefern
(Alternativ zur Liste geht natürlich auch ein Boolean-Flag oder sowas in der Art...)
Aber ich würde das nicht Brute-Force nennen, das klingt so Zeitaufwändig
