Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/21: Рейтинг темы: голосов - 21, средняя оценка - 4.71
Модератор
1638 / 1088 / 487
Регистрация: 17.07.2012
Сообщений: 5,339
1

Реализация поиска в глубину

01.04.2015, 11:25. Показов 4205. Ответов 2
Метки нет (Все метки)

Всем привет. Решил начать учить теорию графов, решаю задачки на одном сайте. Столкнулся с задачкой в которой просто нужно реализовать поиск в глубину.
Скачки
(Время: 1 сек. Память: 16 Мб Сложность: 32%)
Иван Иванович любит ходить на скачки, надеясь на них заработать кругленькую сумму. Ему приглянулась лошадь с номером K, и он решил проверить, сможет ли она выиграть у всех остальных лошадей. Иван Иванович раздобыл информацию, в которой для некоторых пар лошадей сообщается, какая из этих лошадей быстрее. Также он узнал, что у всех лошадей разные скорости.

Требуется написать программу, которая поможет Ивану Ивановичу точно определить может ли выиграть выбранная им лошадь.

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

Входной файл INPUT.TXT содержит в первой строке два целых числа N (1 <= N <= 100) и K (1 <= K <= N), где N – количество лошадей, принимающих участие в скачках, K – номер лошади, на которую хочет сделать ставку Иван Иванович. Следующие строки содержат по два числа X и Y (1 <= X, Y <= N), обозначающие, что лошадь с номером X быстрее лошади с номером Y. Пары X и Y не повторяются. Набор данных завершается строкой, содержащей единственный ноль. Эту строку обрабатывать не надо.

Гарантируется, что информация, раздобытая Иваном Ивановичем, корректна.

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

Выходной файл OUTPUT.TXT должен содержать слово «Yes», если Иван Иванович уверен в своем выигрыше и «No» в противном случае.
Примеры тестов:
INPUT.TXTOUTPUT.TXT
3 1 Yes
1 2 
1 3 
0 
INPUT.TXT OUTPUT.TXT
3 2 No
2 3
0
INPUT.TXT OUTPUT.TXT
4 2 No
3 1
2 3
0
Но на одном тесте превышение ограничения по времени.Помогите пожалуйста.
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <fstream>
#include <vector>
#include <string>
 
using namespace std;
 
int n;
vector <bool> v(110,false);
 
void dfs(vector <vector<int> >& a,int x,int y)
{
    //static vector <bool> v(n,false);
    if (a[x][y]==0 || x==y) return;
    v[y]=true;
 
    bool f=true;
    for (int i=0;i<n;i++)
        if (!v[i])
        {
            f=false;
            break;
        }
    if (f) return;
 
    for (int i=0;i<n;i++)
        if (a[y][i]==1) 
        {
            v[i]=true;
            a[x][i]=1;
            dfs(a,y,i);
        }
 
}
 
int main()
{
    ifstream cin("INPUT.TXT");
    ofstream cout("OUTPUT.TXT");
    int k;
    cin>>n>>k;
    k--;
    vector < vector<int> > a(n,vector<int>(n,0));
    while (true)
    {
        int x,y;
        cin>>x;
        if (x==0) break;
        cin>>y;
        a[x-1][y-1]=1;
    }
 
    for (int i=0;i<n;i++) dfs(a,k,i);
    a[k][k]=1;
    for (int i=0;i<n;i++)
        if (a[k][i]==0)
        {
            cout<<"No";
            return 0;
        }
        cout<<"Yes";
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.04.2015, 11:25
Ответы с готовыми решениями:

Алгоритм поиска в глубину
Мне нужен сам алгоритм, как программа на С ++, желательно с пояснениями к строкам. Может кто-то...

Алгоритмы поиска в глубину
Помогите, пожалуйста, с решением задачи: Постройте линейный алгоритм, который проверяет, есть ли в...

Алгоритмы поиска в глубину и ширину
Помогите с кодом: на входе файл есть файл вида: n m v1 u1 v2 u2 .... vm um Здесь n -...

Граф, алгоритм поиска в глубину
Доброго времени суток, требуется применив алгоритм поиска в глубину, разработать программу поиска в...

2
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
01.04.2015, 14:53 2
Малясь не верный подход..
Ты должен просто запустить dfs из k. И посмотреть можешь ли ты добраться из нее до всех вершин.
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
39
40
41
42
43
44
45
46
47
#include <fstream>
#include <vector>
#include <string>
 
using namespace std;
 
int n;
vector <bool> v(110, false);
 
void dfs(vector <vector<int> >& a, int x)
{
    //static vector <bool> v(n,false);
    v[x] = true;
 
    for (int i = 0; i<n; i++)
        if (a[x][i] == 1 && !v[i])
            dfs(a, i);
 
}
 
int main()
{
    ifstream cin("INPUT.TXT");
    ofstream cout("OUTPUT.TXT");
    int k;
    cin >> n >> k;
    k--;
    vector < vector<int> > a(n, vector<int>(n, 0));
    while (true)
    {
        int x, y;
        cin >> x;
        if (x == 0) break;
        cin >> y;
        a[x - 1][y - 1] = 1;
    }
 
    dfs(a, k);
    v[k] = 1;
    for (int i = 0; i<n; i++)
        if (!v[i])
        {
            cout << "No";
            return 0;
        }
    cout << "Yes";
}
Вот так заходит
1
Модератор
1638 / 1088 / 487
Регистрация: 17.07.2012
Сообщений: 5,339
01.04.2015, 17:05  [ТС] 3
Ромаха, спасибо, все понял.Достаточно пройтись поиском по вершинам и отметить те которые прошли,а если какие-то не прошли значить выводим "No". Accepted!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.04.2015, 17:05

Алгоритм поиска в глубину в ориентированном графе
Добрый вечер,форумчане:) Знаю, что подобная тема встречалась тут довольно часто, но у меня все-таки...

Метод поиска в глубину, в неориентированном графе
Добрый день! Помогите решить задание: Используя метод поиска в глубину, в неориентированном...

Реализация обхода в ширину и глубину бинарного дерева
Как реализовать обход дерева (глубины три, т.е. трех уровневое) в глубину и ширину и что под этим...

Бинарное дерево поиска (определить максимальную глубину)
Всем привет! Делаю лабу, написал основу, но не могу понять, как сделать последний пункт задания,...


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

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

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