Поиск в глубину, вопрос из решенной задачи

387

02 октября 2017, 02:03

Разбираю задачу из мазурока:

e-olimp 4000. Обход в глубину

Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).

Входные данные

В первой строке содержится два целых числа n и s (1≤s≤n≤100), где n — количество вершин графа, а s — выделенная вершина. В следующих n строках записано по n чисел — матрица смежности графа, в которой цифра «0» означает отсутствие ребра между вершинами, а цифра «1» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные

Выведите одно число — искомое количество вершин.

Пример

Входные данные    Выходные данные
5 1
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0         3
0 0 0 0 1
0 0 0 1 0

Я вот до 24-ой строки понимаю, объясните пожалуйста, что происходит после неё:

#include <iostream>
#include <stack>
int main()
{
    int n;
    int s;
    std::cin >> n >> s;
    s--;
    int matrix[n][n];
    stack<int> st;
    int counter = 1;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            std::cin >> matrix[i][j];
    }
    for(int j = 0;j < n; j++)
        if(matrix[s][j] == 1) st.push(j);
    matrix[s][s] = 1;            // <<<=== Вот отсюда становится непонятно
    while(!st.empty())
    {
        int a = st.top();
        st.pop();
        if(matrix[a][a]!=1)
        {
            for(int j = 0; j < n; j++)
                if(matrix[a][j] == 1) st.push(j);
            counter++;
            matrix[a][a] = 1;
        }
    }
    std::cout << counter << std::endl;
}

Answer 1

Сначала стоит напомнить, что компонента связности — это набор вершин, которые достижимы друг из друга. То есть надо посчитать количество вершин, до которых можно дойти из вершины s по рёбрам.

Также напомню для себя, то цикл в строках 21-23 запихивает в стек вершины, непосредственно соединённые с s.

Дальше, в строке 24 (matrix[s][s] = 1), производится нарушение условия входных данных: Гарантируется, что на главной диагонали матрицы всегда стоят нули. То есть по умолчанию там нули, и записью единиц программа возводит для себя какие-то флаги. Какие именно — становится понятно в строках 30 (if(matrix[a][a] != 1)) и 37 (matrix[a][a] = 1): подобным образом алгоритм помечает уже учтённые вершины, чтобы не ходить по ним рекурсивно кругами.

Ну а в целом всё более-менее прямолинейно: берём очередной элемент из стека (изначально там непосредственные соседи вершины s, но позднее он будет пополняться), смотрим, не посещали ли её ранее. Если нет — добавляем её непосредственных соседей в стек, увеличиваем счётчик посещённых вершин на единицу и помечаем вершину как посещённую. Если стек не пуст (то есть мы хоть кого-то добавили, либо не успели разобрать уже добавленных), то возвращаемся в начало цикла, берём очередной элемент из стека и т. д.

Answer 2

Суть алгоритма: рекурсивно обходить все вершины, связные с данной, пока не переберем все вершины, до которых можно добраться. Для этого используется вспомогательный стек, в который заталкиваются еще не испробованные вершины.

  matrix[s][s] = 1;            // <<<=== Вот отсюда становится непонятно

Вершина помечается, чтобы 2 раза не обрабатывать.

if(matrix[a][a]!=1) // необработанная вершина 
        {
            for(int j = 0; j < n; j++) // все ее смежные
                if(matrix[a][j] == 1) st.push(j);//заталкиваются в стек
            counter++;// и ее сосчитали
            matrix[a][a] = 1;
        }

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Плагин для Jquery

Помогите пожалуйста с плагином для JqueryЗадание следующее: Необходимо написать плагин для jQuery, который каждые 30 мс собирает данные о положении...

271

CSS