Задача.Динамич. структуры данных

[Neostat]

Уважаемые форумчане,помогите пожалуйста. Попал я значит в беду.Прошли мы динамич.структуры данных,вернее, только списки лин. односвязные.По этой теме мы все получили задачи. Сейчас вы услышите моё отчаяние...У всех кроме меня задача плана: "Упорядочить список по возрастанию значения поля записи info"...
А мне дали вот такую задачу:"
Пусть имеется N городов и задан список пар городов (i,j),между которыми существует прямая дорога.Напечатайте список городов ,которые напрямую сообщаются более чем с тремя городами."
И да,я скажу честно.Я понятия не имею как её решать,не знаю даже с какого бока подойти.После рытья интернета я понял,что здесь что-то связано с графами и матрицой смежности.И вроде как я понял, это все должно быть в виде дерева? В общем помогите пожалуйста чем сможете.Хотя бы скажите как и в виде чего мне все это хранить.Я правда понятия не имею.Или может я не нашел какой-нибудь ресурс ,где есть разбор аналогичных задач....
Буду очень благодарен любой помощи.

И все-таки не могу я понять,с какого бока подходить к этой задаче,как вообще её решать с помощью односвязного списка.Как хранить связь между городами ,(дан список пар городов). Это что дерево должно быть?Или что?Подскажите пожалуйста,уже неделю не могу её решить.Всем в моей группе дали примитивные задачи типа :"Упорядочить список по возрастанию значения поля info". А мне эту ,так я копал интернет и понял,что это вроде как через матрицу смежности должно решаться,но мы такого нигде ещё не проходили.На лекциях и практики были разбор только примитивных задач.Моя большая проблема в том,что я не понимаю,как это все хранить.Я буду очень признателен,если кто-нибудь сказал,а лучше бы показал как всю эту информацию хранить в списке...Алгоритм поиска городов,которые напрямую связаны не менее чем с тремя я попробую придумать сам.Мне правда очень нужна Ваша помощь.Помогите пожалуйста.

P.s. Мне не лень решать задачи,я всегда подхожу к этому делу с интересом,но тут я стою на мертвой точке. Я даже к преподу подходил,но она мне толком и не смогла ничего сказать,только покивала,что-то на счет матрицы смежности. Просто я не могу понять,как хранить исходные данные ,вот я пытался на листке делать примерно так:
Дано: 4 города например. Будем их так и называть: Город 1,город 2 и т.д
А вот связь между ними:
1 2
1 4
2 4
3 4

И как эти пары мне в динамич. структуры запихнуть,если честно я вижу здесь 4 односвязных лин. списка или я что-то не понимаю...
Из 1 -> 2 - >4 это ещё терпимо,но как мне из 2->4 и 3->4 загнать в единый целый список,дерево или что ещё может быть?
В общем полный тупик и непонимание этой задачи...

[BDA]

Первое, что пришло в голову:
Считываем пары городов и помещаем в один линейный список, причем упорядочиваем номера городов в паре по возрастанию и при добавлении проверяем, что такой пары в списке еще не было. Затем N раз проходим по списку, чтобы выяснить, со сколькими городами связан i-й город.

Второе:
Заводим N списков и при считывании пары (i, j) в i-й список помещаем j-й город и наоборот, проверяя, что такого города еще нет в рассматриваемом списке. Затем выводим те города, соответствующие списки которых достаточно длинны.

[Neostat]

То есть,во втором варианте мы грубо говоря будем иметь матрицу примерно такого вида:
В - Волгоград , М - Москва , О - Орёл , Л - липецк
Сама матрица будет я так понимаю из списков?

Например первый элемент матрицы это список
Head->|В,next|->|M,next|->Nill ?

(В,М) (В,О)
(М,О) (В,Л)

Или я что то не понял, как то не могу вот это немного предстасить :
"пары (i, j) в i-й список помещаем j-й город и наоборот".

Вот у нас i-й список,мы ввели пару городов (М,В), мы берем и передвигаем указать на след. элемент,в нашем случае запись ->|Москва|->nill .
А в j-й список |Волгоград| -> nill?

То есть в матрице будет в (i,j) элемете храниться два разных списка ?Но что будет дальше как-то не могу понять.

Допустим вводим след пару городов (В,Л)
i-й : -> |Липецк| ->nill
j-й : ->|Волгоград|->nill

И тут мы сравниваем,если (i,j) = (j,i) ,хотя мне кажется я какой-то бред написал

[BDA]

Пусть есть 3 города: 0; 1; 2
Соответствующие списки (массив списков): nil; nil; nil

Подаются пары городов:
(0, 1)
Списки: 1->nil; 0->nil; nil

(1, 2)
Списки:1->nil; 0->2->nil; 1->nil

(2, 1)
Списки: не изменились, так как в списке 1го уже есть 2й город, в списке 2го - 1й

И т.д.

[Neostat]

спасибо большое.
А если бы мы добавили вместо (2,1) пару городов (2,4), то получилось бы:

Списки: 1-> nil; 0->2->nil; 2-> nil; 0->2->4-> nil ?


А Ваш первый вариант представляет собой :
Пусть есть 3 города: 0; 1; 2 и список:nil;
Подаются пары городов:

(0,1)
0->1-nil

(1,2)
0->1->2->nill

Я так понял?

[BDA]

А если бы мы добавили вместо (2,1) пару городов (2,4), то

Во-первых, если есть номер 4, то всего городов (и списков) будет 5 (нумерация с 0).
Во-вторых, номер 4го города должен был попасть в список 2го.
То есть, списки выглядели бы так:
1->nil; 0->2->nil; 1->4->nil; nil; 2->nil
(список 3го города пуст)

первый вариант представляет собой

Подаются пары:
(0, 1)
Список: (0, 1) -> nil

(0, 2)
Список: (0, 1) -> (0, 2) -> nil

(2, 1)
Список: (0, 1) -> (0, 2) -> (1, 2) -> nil

Элемент списка - пара чисел, а не одно число.

UPD
Пожалуйста

[Neostat]

Все понял,ещё раз огромное спасибо.Извините за то,что так тупил.Оказывается я не так понял условие. Теперь все понятно.

[Poma][a]

Первый вариант классный. Я сразу о 2-Ом подумал.
Можно тогда его еще сортануть и совсем ляпота выйдет. За один проход ответ получим

[BDA]

Poma][a, чтобы за 1 проход получить ответ, придётся, пожалуй, сохранять в список не дорогу, а направление, то есть помещать в список пары (i, j) и (j, i). Тогда после сортировки легко будет определяться количество дорог (выходящих из города направлений).

[Poma][a]

Я именно это и имел в виду, видимо, я не совсем правильно прочитал Ваш вариант, пардон