петли и параллельные ребра в неор.графе

[FasterHarder]

Всем хай! Сходу к делу!

Определение:
Ребра, имеющие одинаковые концевые вершины, называются параллельными.
Например, ребро, соединяющее вершины №4 и №8 и ребро, соединяющее вершины №8 и №4 - являются параллельными. Тут вроде все понятно. Также в графе может быть более 2ух параллельных ребер для двух вершин.

Определение:
Ребро, концевые вершины которого совпадают, называется петлей. Например, задается как 3-3, т е ребро выходит из вершины №3 и заходит в вершину №3.

Вопрос: две петли одной вершины можно считать параллельными ребрами??
-----------------------------------------------------
Второй вопрос.
Дано несколько сотен вершин неориентированного графа. + задаются все ребра графа через вершины. Надо проверить, содержит ли граф || ребра.
формат входных данных типа такого:
a b
1 2
3 17
4 6
2 1
5 5
...
а - кол-во вершин графа, b - кол-во ребер.

Алгоритм. Можно, конечно, тупо выделить память для динамической матрицы размером a x a (ну, т е формировать матрицу смежности) и при считывании очередного ребра в соот-щей ячейке ставить 1, как будто-то это не ребро, а ДУГА + параллельно проверять симметричную ячейку, если и там и там стоит по 1 - все, конец обработке - граф содержит || ребра.
1. А, что делать с петлями??
2. Есть более совершенный алгоритм решения?

спс за внимание

Сообщение отредактировано: FasterHarder - 22.02.21, 11:55

[Akina]

Цитата FasterHarder @ 22.02.21, 11:54

Вопрос: две петли одной вершины можно считать параллельными ребрами??

Конечно. Не просто "можно считать" - они таковые и есть...

Цитата FasterHarder @ 22.02.21, 11:54

2. Есть более совершенный алгоритм решения?

В неориентированном графе порядок вершин неважен. Так что обработать, и для вершин, где конечная точка меньше по индексу - перевернуть. И результат - отсортировать.

Сообщение отредактировано: Akina - 22.02.21, 17:46

[FasterHarder]

Цитата Akina @ 22.02.21, 17:46

Конечно. Не просто "можно считать" - они таковые и есть...

ок, понял, спс

Цитата Akina @ 22.02.21, 17:46

В неориентированном графе порядок вершин неважен. Так что обработать, и для вершин, где конечная точка меньше по индексу - перевернуть. И результат - отсортировать.

про неор.граф понятно, что порядок не важен вершин, смущает другое - предложение отсортировать после ввода входных данных (на др.форуме была такая же идея). Но сортировка ведь далеко не самая быстрая операция. В моем варианте анализ происходит НА ЛЕТУ(!) и в половине случаев обработка сразу прервется при нахождении хотя бы одной пары || ребер. Здесь же придется сначала ВСЕ прочитать, потом сортировать...не уверен, что это будет производительнее

для учета петель ведь можно завести одномерный динамический массив, состоящий из "а" элементов (а - кол-во вершин графа). Обнулить все элементы и делать +1, когда встретилась петля. Как только стало в любом элемента == 2 - встретилась петля 2 раза для одной вершины - конец обработке.


в общем насчет сортировки не уверен...+этих способов сортировки "тысячи"

[MBo]

В мап клади пары, отсортированные, как Akina сказал. Уже есть такая пара - всё, приехали. Обработка петель ничем не отличается

[Akina]

Цитата FasterHarder @ 22.02.21, 19:43

смущает другое - предложение отсортировать после ввода входных данных (на др.форуме была такая же идея). Но сортировка ведь далеко не самая быстрая операция.

Чегой-то после-то? непосредственно в процессе...

Цитата FasterHarder @ 22.02.21, 19:43

встретилась петля 2 раза для одной вершины - конец обработке.

Вот что-то в исходном состоянии заданного вопроса чего-то типа "убедиться, что параллельные рёбра отсутствуют" - не вижу. Тогда и этот этап - проверка на дубликат,- тоже распрекрасно выполняется в процессе ввода.

[FasterHarder]

Цитата MBo @ 22.02.21, 21:18

В мап клади пары, отсортированные

а, если язык "чистый" СИ)
но, на самом деле язык С++, поэтому все эти шаблоны вроде можно юзать. Но я работаю с СИ раз так в 10 больше, чем с С++, поэтому плохо умею мыслить в терминах stl.

Цитата Akina @ 23.02.21, 07:44

Чегой-то после-то? непосредственно в процессе...

сортировать на лету? чуть позже вернемся к сортировке

Цитата Akina @ 23.02.21, 07:44

Вот что-то в исходном состоянии заданного вопроса чего-то типа "убедиться, что параллельные рёбра отсутствуют" - не вижу.

Здесь не понял тебя. Если после проверки на || ребер таких нет, то автоматически заданный граф НЕ содержит || ребер

Я вот совсем НЕ выкупаю, зачем здесь ЧТО-ТО сортировать???!
Берем СТЛ. Там ведь есть шаблон "множество уникальных значений" (сет или мап или еще как-то называется - вообще не суть). После считывания ребра (2 целых числа) ставим меньшее слева, а большее справа и запихиваем в множество. Но перед тем, как запихнуть, проверяем, а нет ли такого элемента в множестве. Если есть, значит попытка добавить дубликат, что равносильно тому, что в графе появилось || ребро - все, конец обработке!

Зачем здесь что-то сортировать?????

Добавлено 23.02.21, 10:42
на всякий случай уточню относительно постановки задачи:

Цитата FasterHarder @ 22.02.21, 11:54

Надо проверить, содержит ли граф || ребра.

т е ответом должно быть "Да" или "Нет", т е не нужно находить эти || ребра, важен сам факт

[Akina]

Цитата FasterHarder @ 23.02.21, 10:37

зачем здесь ЧТО-ТО сортировать???!

Чтобы:

1) быстрее вставлять очередную запись в сортированный список, сохраняя сортировку
2) при этом быстрее выполнять проверку на дублирование

Глупо вводить всё, когда уже на середине ввода станет возможно дать ответ.

[FasterHarder]

Akina, а я вот считаю, что сортировка здесь НЕ нужна вообще - и так все прекрасно сработает
здесь вообще о сортировке даже речи быть не может

есть множество (stl-ское какое-нибудь) и через него все можно сделать. Вот единственная проблема, что я плохо помню устройство этих контейнеров set/map и пр., поэтому не хочу спорить сильно)

зы: а вообще я ведь реализовал изначально через заполнение матрицы смежности 0 и 1 + доп.вектор для петель - прожка прошла все тесты по времени и производительности (не забыл поставить register для счетчиков циклов ) - можно считать, что на "чистом" си была выполнена. И считывание данных заканчивалось, как только была обнаружена 1ая пара || ребер. Все ок
------------------------------------------------------------
краем глаза прочитал про stl-ский set: пишут, что при добавлении в множество автоматически происходит сортировка в порядке возрастания. + перед тем, как добавить элемент в сет, можно узнать через find, а существует ли такое значение в сете.

в общем я НЕ понимаю, зачем здесь что-то сортировать вручную

[OpenGL]

В кои-то веки согласен с FasterHarder. Сортировать не надо, можно просто в std::set/std::unordered_set очередное ребро запихивать.

[AVA12]

Убрать сортировку "под капот" - не значит избавиться от нее. Даже если это не сортировка, а хеширование - все равно полезно помнить про накладные расходы.

В данной задаче, вероятно, сортировка и правда не нужна. Если для каждой вершины меньше десятка инцидентных ей ребер, то можно для каждой вершины завести неупорядоченный односвязный список смежных вершин и искать элементы простым перебором.

Цитата

я ведь реализовал изначально через заполнение матрицы смежности 0 и 1 + доп.вектор для петель

А зачем доп.вектор для петель? Петля - это, по сути, вершина, смежная сама с собой, так что матрицы достаточно.