DjangoBB LoFi version

Начало » Python для новичков » Параллельные рёбра

T0t0ro

Март 20, 2019 21:38:15

Ориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра.
Входные данные
Сначала вводятся числа n ( 1 ≤n ≤100) – количество вершин в графе
и m ( 1≤10 000) – количество ребер. Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите «YES», если граф содержит параллельные ребра, и «NO» в противном случае.
Примеры входные данные
5 3
2 5
3 1
3 2
выходные данные
NO

py.user.next

Март 21, 2019 00:35:47

Параллельные рёбра - это типа 5 3 и 3 5. То есть рёбра у которых одни и те же вершины.

Главное, что тут не надо считывать всё. Можно использовать множество set() в которое добавлять отсортированные пары вершин. Как только пара уже содержится во множестве, можно прерывать считывание и писать YES. Если рёбер в графе миллион, это имеет значение. Тут же их может быть 10000, но при этом на первых же двух рёбрах может быть то, что они параллельные, и поэтому считывать дальше ничего не надо.

T0t0ro

Март 21, 2019 06:17:56

py.user.next
Параллельные рёбра - это типа 5 3 и 3 5. То есть рёбра у которых одни и те же вершины.Главное, что тут не надо считывать всё. Можно использовать множество set() в которое добавлять отсортированные пары вершин. Как только пара уже содержится во множестве, можно прерывать считывание и писать YES. Если рёбер в графе миллион, это имеет значение. Тут же их может быть 10000, но при этом на первых же двух рёбрах может быть то, что они параллельные, и поэтому считывать дальше ничего не надо.

Да я понимаю. Просто догнать не могу, как допустим циклом правильно перебор сделать

py.user.next

Март 21, 2019 07:22:13

  
>>> def f():
...     s = input()
...     n, m = map(int, s.split())
...     st = set()
...     for _ in range(m):
...         s = input()
...         a, b = map(int, s.split())
...         t = min(a, b), max(a, b)
...         if t not in st:
...             st.add(t)
...         else:
...             break
...     if len(st) == m:
...         print('NO')
...     else:
...         print('YES')
... 
>>> f()
5 3
2 5
3 1
3 2
NO
>>> f()
5 2
2 5
3 1
NO
>>> f()
5 2
3 1
1 3
YES
>>> f()
5 4
1 2
3 4
5 2
2 1
YES
>>>

T0t0ro

Март 21, 2019 19:22:38

py.user.next

ммм, правда хороший цикл, возьму себе на заметку. Спасибо!