47
правок
Изменения
м
Код раскрашен
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах
'''bool ''' dfs('''int ''' u)
{
'''if''' (u == t)
'''return''''' true''; visited[u] = ''true''; //помечаем вершину как пройденную
'''for''' (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам
'''if''' (!'''not''' visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
'''if''' (dfs(v))
'''return''''' true''; '''return''''' false'';
}
'''int ''' main()
{
... //задание графа G с количеством вершин n и вершин S и T.
visited.assign(n, ''false''); //в начале все вершины в графе ''не пройденные''
'''if''' (dfs(s))
std::out << "Путь из S в T существует";
=== Реализация ===
vector<'''bool'''> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах '''int ''' k = 0;
void dfs('''int ''' u)
{
k--;
visited[u] = ''true''; //помечаем вершину как пройденную
'''for''' (v таких, что (u, v) — ребро в G) //проходим по смежным с u вершинам
'''if''' (!'''not''' visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}
'''int ''' main()
{
... //задание графа G с количеством вершин n и вершин S и T.
visited.assign(n, ''false''); //в начале все вершины в графе ''не пройденные''
k = n;
'''for''' ('''int ''' i = 0; i < '''to''' n; i++- 1)
dfs(i);
'''if''' (k == 0)
