Граф представляется матрицей смежности (или матрицей весов), структура хранения – статический двумерный массив. Имеются

@zaharkiy · Регистрация: 30.05.2022

Author24 — интернет-сервис помощи студентам

Граф представляется матрицей смежности (или матрицей весов), структура хранения – статический двумерный массив.
Имеются n городов, некоторые из них соединены дорогами. Определить, из каждого ли города можно попасть в остальные.

Имеется карта городов и посёлков, связанных сетью дорог. Некоторые посёлки связаны лишь с одним населённым пунктом – это окраины. Жители окраин ежегодно переселяются в соседние посёлки и города, после чего посёлки пустеют и удаляются с карты, но при этом могут образоваться новые окраины. В следующем году всё повторяется, если окраины еще остались. Определить, какие города и поселки останутся на карте после того, как исчезнут все окраины.

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

@FasterHarder · 31.05.2022, 01:52

возможно, что 1-ая задача про компоненты связности графа, если k = 1, то, да. В этом поможет BFS / DFS.
зы: вроде только неор графов

Добавлено через 7 минут
по 2-ой задаче.
вроде ( ! ) дропать нужно вершины со степенью = 1 + у смежной вершины ( она единственная, это гарантируется ) степень - 1.

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

все имхо

@zaharkiy 0 / 0 / 0 Регистрация: 30.05.2022 Сообщений: 1
		1
	Граф представляется матрицей смежности (или матрицей весов), структура хранения – статический двумерный массив. Имеются 30.05.2022, 18:44. Показов 404. Ответов 1 Метки графы, си++ (Все метки) Граф представляется матрицей смежности (или матрицей весов), структура хранения – статический двумерный массив. Имеются n городов, некоторые из них соединены дорогами. Определить, из каждого ли города можно попасть в остальные. Имеется карта городов и посёлков, связанных сетью дорог. Некоторые посёлки связаны лишь с одним населённым пунктом – это окраины. Жители окраин ежегодно переселяются в соседние посёлки и города, после чего посёлки пустеют и удаляются с карты, но при этом могут образоваться новые окраины. В следующем году всё повторяется, если окраины еще остались. Определить, какие города и поселки останутся на карте после того, как исчезнут все окраины. Помогите, если не сложно написать программу, не знаю как сделать задание. 0

@FasterHarder 361 / 262 / 107 Регистрация: 28.04.2015 Сообщений: 1,608
	31.05.2022, 01:52	2
	возможно, что 1-ая задача про компоненты связности графа, если k = 1, то, да. В этом поможет BFS / DFS. зы: вроде только неор графов Добавлено через 7 минут по 2-ой задаче. вроде ( ! ) дропать нужно вершины со степенью = 1 + у смежной вершины ( она единственная, это гарантируется ) степень - 1. Все это работает до тех пор, пока есть вершины со степенью = 1. вроде теор. все может уничтожиться и превратиться в прах ( например, когда на старте 2 вершины, связанные 1ой дорогой, они обе вырождаются в ничто, оставляя после себя ничто ) все имхо 0