Если судить по примеру вывода после разбора - то все-таки там дерево, а не граф. Этот вопрос принципиальный с точки зрения вывода: показанный пример выводит дерево. А как выводить граф?

Связный граф без циклов и есть дерево.
Если есть циклы — надо сообщить об этом без вывода зависимостей, я так понял.

В примере nickless'а выше[A->{B C}->D на языке dot]  циклических зависимостей как раз и нет. Потому как D зависит от B и C, B зависит от A и C зависит от A. и других зависимостей нет.
нет цикла. граф здесь ориентированный, и это надо учитывать.
я безсовестно заменил в примере графа длинные названия ItemN... на A...

Добавлено @ 17:43 
Кстати, если под "выводом зависимостей на экран" подразуметь (подобно tsort(1)) 

и забить на красивые отступы, то эта самая топологическая сортировка как раз даст искомый результат, то у nickless'овского графа A->{B C}->D будет два валидных выхода:

и




Это сообщение отредактировал(а) Mayk - 18.1.2007, 17:46

Честно говоря, мне не видится эта задача слишком сложной с точки зрения создания самой структуры зависимостей.

Но пост Maykа как раз о той проблеме, которую я вижу: как это правильно вывести, если один потомок зависит от двух предков сразу? Или данная ситуация считается ошибочной? Если немного расширить исходные данные:
A B C D
B E F
C E F

То как это должно быть выведено?
A
 B
  E <--- Т.е. по два раза вывести? Или это ошибочные данные
  F <---
 C
  E <---
  F <---
 D

 Или надо так вывести (полный бред по-моему)
A
 B C
  E F

Не совсем понятны условия.

Если это обычное дерево - то не намного сложнее дерева подкаталогов получится 

Чтоб выполнить эти пункты логику программы, думаю, надо основвывать на паттерне "Composite" (Компоновшик) (см. книгу четырёх "Design Patterns. Elements of Reusable Object-Oriented Software.", есть на русском). Это не только прояснит логику, но и к тому же сразу скажет проверющему о хорошей квалификации программиста. Было бы время, я бы с удовольствием наваял решение. Хорошая задачка 

Дело не в написании парсера... Файл читается вполне стандартными средствами - оператором >> в строковые переменные.
Дело именно в логике...
Но логика тож не сильно сложная...
Так как скорость в качестве критерия не фигурирует (видимо не случайно), то нужно использовать стандартный список list из STL
list<string> children - это список детей...
struct element
{ string родитель;
   list<string> children;
}
list<element> tree; // фактически список-списков...
После прочтения файла он просто выводится на экран в цикле...


Для отслеживания циклических связей досточно проверять каждого дитятю на совпадение с родителем...
Алгоритм скорости вроде O(n^2)

codelord, 
Готовь тесты, чтобы убедиться в работоспособности =) Мож найдется время вечерком - напишу чего-нить.

Добавлено @ 19:28 
Так действительно интересно, сколько давалось на эту задачку времени?

Блин, времени вообще выделить не могу на это дело. Сейчас на работе полный аврал, плюс диплом доделывать надо. Единственное сложное и интересное место в этой задаче - это сортировка частично упорядоченного множества (упорядоченность заключается в правилах "кто чей родитель"). 
Ее алгоритм мы в универе давно еще проходили. Могу быстренько накидать, если нужно.

imho это замыкание множества атрибутов над множеством функциональных зависимостей, алгоритм из области реляционных баз данных.



к примеру имеем множество функциональных зависимостей:
A->D
AB->E
BF->E
CD->F
E->C

находим замыкание для множества атрибутов:
AE

Получаем:
{AE, AEDC, AEDCF}

Вроде так, если ничего не напутал.

codelord, где-то валяются исходники, но к сожалению на Delphi. если нужно - стучи в ПМ.

p.s.: imho странноватое тестовое задание. std::set + рутина, особые знания языка или ООП  такое задание не покажет, зато напрягает большое кол-во требований по интерфейсу(в какой строке ошибка и т.п., требование к возможности реутилизации кода). imho надо быть осторожней с этим работодателем. 

Если используется стандартные контейнеры, то STL уже имеет нужные сортировки... Нужно просто использовать...