Если я правильно понимаю, вы пытаетесь найти поперечный край, два конца которого не являются предками друг друга, в ориентированном графе. В этом случае вы можете изменить алгоритм DFS, чтобы получить набор поперечных ребер. Поскольку алгоритм DFS работает одинаково как в неориентированном графе, так и в ориентированном графе, вам нужно записать обнаруженное время и время окончания одной вершины и добавить функцию, которая сравнивает эти значения одной вершины с другой вершиной. Например, дуга e имеет два конца u и v. При проверке соседа u вершины v, следующей за e, если u уже посещен и завершен (т. Е. У u законченное время), а время начала u меньше время начала v, то е является поперечным ребром. Как только алгоритм обнаружит, что дуга является перекрестной кромкой, вы можете просто добавить эту дугу к набору перекрестных ребер и вывести ее в конце.