С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
#1

Время обзода в глубину - C++

10.01.2014, 08:43. Просмотров 175. Ответов 2
Метки нет (Все метки)


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n,s,b,c,d=0,a[101][101],v[101];
void dfs(int z);
int main()
{
    memset(v,0,sizeof(v));
    cin >> n >> s;
    while(true)
    {
        cin >> b;
        if (b == 0)
            break;
        cin >> c;
        if (c == 0)
            break;
        a[b][c] = 1;
        a[c][b] = 1;
    }
    dfs(s);
    if (d == n - 1)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}
void dfs (int z)
{
    for (int i = 0; i < n; i++)
        if (a[z][i] == 1 && v[i] == 0)
        {
            v[i] =1;
            d = d + 1;
            dfs(i);
        }
}
Не прохожу по времени.
Что поменять? Или можно быстрее ДФСа?
З.Ы. Да, ошибся в названии темы.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2014, 08:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Время обзода в глубину (C++):

Поиск в глубину - C++
Объясните плз поиск в глубину с примером. Сам много реалихаций нашел, но до конца не могу разобраться, может у кого есть примерчик хороший....

Поиск в глубину - C++
Здравствуйте. Как реализовать поиск кратчайшего пути в невзвешенном графе через поиск в глубину? Пробовал сделать так const...

Поиск в глубину - C++
Помогите с заданием пожалуйста. Число 1 можно записать как сумму n чисел вида 1 / i, где i - натуральное число. Например, для n = 3 имеем...

поиск в глубину - C++
Дали задание реализовать поиск в глубину.Пробую релизовать по e-maxx http://e-maxx.ru/algo/dfsно не получается. vector&lt;char&gt; used; int...

Поиск в глубину - C++
&quot;В рождественскую ночь Санта-Клаус спускается по каминной трубе и раскладывает детям подарки. Кровати в комнате стоят очень плотно. Чтобы...

графы. поиск в глубину - C++
Здраствуйте. Вот такая задача N шестеpенок пpонумеpованы от 1 до N (N ≤ 10). Заданы M (0 ≤ M ≤ 45) соединений паp шестеpенoк в виде (i,...

2
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.01.2014, 09:04 #2
dfs на 100 вершинах так, чтобы не заходил в секунду...
0
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
10.01.2014, 11:23  [ТС] #3
Цитата Сообщение от salam Посмотреть сообщение
dfs на 100 вершинах так, чтобы не заходил в секунду...
Ну, криво написал, согласен. Поправите?

Добавлено через 58 минут
UP.

Добавлено через 50 минут
UP.

Добавлено через 13 минут
Цитата Сообщение от salam Посмотреть сообщение
dfs на 100 вершинах так, чтобы не заходил в секунду...
И кстати, ДФС на 1000 вершинах прыгает как горный козел - Легко и непринужденно.

Добавлено через 9 минут
программа решена, закрывать
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2014, 11:23
Привет! Вот еще темы с ответами:

Обход графа в глубину - C++
Как сделать обход этого графа в глубину ?

Итеративный поиск в глубину - C++
Здравствуйте! Вопрос связан с поиском в графе. Меня интересуют идеи решения или ссылка на литературу. Пожалуйста, подскажите... ...

Поиск в глубину. Графы. С++ - C++
Задана ,допустим, такая матрица смежности 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 Node.h #pragma once

Реализация поиска в глубину - C++
Всем привет. Решил начать учить теорию графов, решаю задачки на одном сайте. Столкнулся с задачкой в которой просто нужно реализовать поиск...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.