Форум сайта python.su
Ориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра.
Входные данные
Сначала вводятся числа n ( 1 ≤n ≤100) – количество вершин в графе
и m ( 1≤10 000) – количество ребер. Затем следует m пар чисел – ребра графа.
Выходные данные
Выведите «YES», если граф содержит параллельные ребра, и «NO» в противном случае.
Примеры входные данные
5 3
2 5
3 1
3 2
выходные данные
NO
Офлайн
Параллельные рёбра - это типа 5 3 и 3 5. То есть рёбра у которых одни и те же вершины.
Главное, что тут не надо считывать всё. Можно использовать множество set() в которое добавлять отсортированные пары вершин. Как только пара уже содержится во множестве, можно прерывать считывание и писать YES. Если рёбер в графе миллион, это имеет значение. Тут же их может быть 10000, но при этом на первых же двух рёбрах может быть то, что они параллельные, и поэтому считывать дальше ничего не надо.
Офлайн
py.user.next
Параллельные рёбра - это типа 5 3 и 3 5. То есть рёбра у которых одни и те же вершины.Главное, что тут не надо считывать всё. Можно использовать множество set() в которое добавлять отсортированные пары вершин. Как только пара уже содержится во множестве, можно прерывать считывание и писать YES. Если рёбер в графе миллион, это имеет значение. Тут же их может быть 10000, но при этом на первых же двух рёбрах может быть то, что они параллельные, и поэтому считывать дальше ничего не надо.
Офлайн
>>> 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 >>>
Офлайн
py.user.nextммм, правда хороший цикл, возьму себе на заметку. Спасибо!
Офлайн