Транзитивность неориентированного графа
Напомним, что граф называется транзитивным, если всегда из того, что вершины u и v соединены ребром и вершины v и w соединены ребром следует, что вершины u и w соединены ребром.
Проверьте, что заданный неориентированный граф является транзитивным.
Сначала вводятся числа n ($1 \le n \le 100$) – количество вершин в графе и m ($1 \le m \le n(n - 1) / 2$) – количество ребер. Затем следует m пар чисел – ребра графа.
Выведите «YES», если граф является транзитивным, и «NO» в противном случае.
5 1 2 5
YES
Понятие транзитивности — это формальное отражение принципа «друг моего друга — мой друг». Если вершины графа — люди, а ребра соединяют друзей, то принцип «друг моего друга — мой друг» выполняется в транзитивных графах, и только в них. Аналогичный принцип встречается и во многих других ситуациях, например, если у вас есть какие-то предметы, и некоторые из них «одинаковые», то обычно вы подразумеваете, что если предметы A и B «одинаковые», и B и C тоже «одинаковые», то предметы A и C тоже должны быть «одинаковыми» — т.е. граф «одинаковости» должен быть транзитивным.
Понятие транзитивности можно применять как для ориентированных, так и для неориентированных графов. Неориентированный граф является транзитивным тогда и только тогда, когда каждая его компонента связности является полным графом (но в этой задаче это не нужно). У ориентированных графов все интереснее (и соответствует не отношению «одинаковости» элементов, потому что «одинаковость» обычно неориентирована, а скорее отношению «один элемент меньше другого»).