задача нужны идеи

← →
sat © (2006-12-14 00:47) [0]

Путь в графе

Задан ориентированный граф с N вершинами и M дугами (2 ≤ N ≤ 1000000, 0 ≤ M ≤ 1000000). Вершины графа пронумерованы, начиная с единицы. Некоторые пары вершин могут быть соединены более чем одной дугой, допускаются петли. Требуется определить, существует ли путь из вершины A в вершину B (1 ≤ A, B ≤ N, A ≠ B) и в случае положительного ответа найти один из таких путей. При решении задачи использовать самостоятельно разработанный класс «очередь».
Входные данные: текстовый файл PATH.IN содержит N+2 строки. Первая строка файла содержит значения N и M, вторая строка – значения A и B. Каждая из последующих строк описывает дуги, выходящие из одной вершины, и содержит число таких дуг, а также номера вершин, в которые эти дуги входят. Числа в строке разделяются одним или несколькими пробелами.
Выходные данные помещаются в текстовый файл PATH.OUT. В случае, если искомого пути нет, единственная строка этого файла должна содержать текст ’No’. Если путь найден, первая строка файла должна содержать текст ’Yes’, а вторая – номера всех вершин (включая начальную и конечную), через которые проходит найденный путь. Числа в этой строке должны разделяться одним или несколькими пробелами.
Ограничения на время выполнения: 20 секунд на тест (компьютер класса Celeron-315, 1 Gb RAM)
Примеры входных данных Примеры выходных данных

← →
MBo © (2006-12-14 06:42) [1]

Человеку, который знаком с термином "граф", должны быть известны и фразы "поиск в ширину", "алгоритм Дейкстры", "алгоритм Флойда"

← →
iZEN © (2006-12-14 07:49) [2]

шаблонное решение

← →
boriskb © (2006-12-14 08:09) [3]

MBo © (14.12.06 6:42) [1]
Человеку, который знаком с термином "граф", должны быть известны и фразы "поиск в ширину", "алгоритм Дейкстры", "алгоритм Флойда"

:))
Мне вот известно слово "автомобиль". Известны так же слова "карбюратор", "коробка передач", но это ни коим образом не помогает мне в моем абсолютном неумении чинить автомобиль :)

← →
Alx2 © (2006-12-14 08:39) [4]

>boriskb © (14.12.06 08:09)

Простительно, так как при всем этом не автослесарь. :)

"Аксакалы, в ваши времена душманы не минировали дорог" (с) анекдот.

← →
MBo © (2006-12-14 09:46) [5]

>boriskb © (14.12.06 08:09) [3]
Есть ведь элементарные вещи, которые непосредственно связаны с каждым понятием.
Если кто-то хоть чуть знаком с автомобилем, то понимает, что если он не заводится, то нужно проыерить, есть ли бензин, проверить аккумулятор, дверками хлопнуть ;)
Любой, кто имеет дело с массивами, знает, что такое их индексация, умеет обойти массив в цикле
Вот и для графов есть базовые понятия - вершина, ребро(дуга), связанные вершины, и, конечно, обходы графа.

Лабораторная задача. Решается влоб методом, описанным в методичке.

задача нужны идеи Найти похожие ветки