Решение задачи 11.
Для решения задачи достаточно определить, является ли связным граф, определяемый матрицей смежности, элементы которой а[i,j] равны 1, если люди с номерами i и j знакомы и равны 0 иначе. Граф называется связным, если существует путь между любыми парами его вершин. Понятно, что путь между вершинами i и j в таком графе и определяет возможную последовательность знакомств, позволяющих познакомить людей с номерами i и j.
Для определения связности графа можно воспользоваться методом поиска в ширину, который состоит в следующем.
На начальном этапе в очередь помещается некоторая начальная вершина, например вершина с номером 1.
На каждой из следующих итераций (пока очередь не пуста) выполняются следующие действия:
- извлекается вершина из очереди;
- определяются вершины, ей смежные и которые в очереди еще не были, и помещаются в очередь.
Если в результате таких действий все вершины побывали в очереди (а для этого удобнее подсчитывать количество вершин, там побывавших), то граф связен, иначе не связен. Для маркировки вершин, побывавших в очереди, можно использовать массив размера N с элементами 0 и 1.
|
