Для любителей графов

@Zivaka · Регистрация: 02.11.2014

Студворк — интернет-сервис помощи студентам

Иван Иванович любит ходить на скачки, надеясь на них заработать кругленькую сумму. Ему приглянулась лошадь с номером K, и он решил проверить, сможет ли она выиграть у всех остальных лошадей. Иван Иванович раздобыл информацию, в которой для некоторых пар лошадей сообщается, какая из этих лошадей быстрее. Также он узнал, что у всех лошадей разные скорости.

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

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

Пример:
1 тест
5 5
1 2
2 3
3 4
5 1
0

Yes

2 тест
4 2
2 3
4 1
0

No
3 тест
3 1
1 2
3 2
0

No

Помогите придумать, как использовать графы.

@dmitrydm · 30.03.2015, 23:35

задали именно эту задачу! присоединяюсь и прошу помочь!

@mat_for_c · 31.03.2015, 00:40

Расскажу идею.
Пусть лошадь А быстрее лошади Б. Тогда для графа будет существовать дуга от вершины А к вершине Б. Граф представляется в виде квадратной несимметричной матрицы (0 - нет дуги, 1 - есть дуга, диагональ - 0).
Если ставка идет на лошадь Х, то нам нужно проверить, возможно ли посетить из вершины Х все остальные вершины. Если это возможно, то тогда лошадь Х самая быстрая, иначе непонятно, то бишь "No".

@Zivaka · 01.04.2015, 22:12 **[ТС]**

Как-то так получилось, кому интересно.

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
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int n;
vector <bool> v(110, false);
 
void dfs(vector <vector<int> >& a, int x)
{
    v[x] = true;
 
    for (int i = 0; i<n; i++)
        if (a[x][i] == 1 && !v[i])
            dfs(a, i);
 
}
 
int main()
{
    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";
    return 0;
}

@VyacheslavSqrt · 13.07.2021, 10:34

Тоже решение, но строчек меньше)

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
#include <bits/stdc++.h>
using namespace std;
int w[105][105], visited[105], n, k;
 
void dfs(int j) {
    visited[j] = 1;
    for (int i = 0; i < n; i++) {
        if (w[i][j] && !visited[i]) dfs(i);
    }
}
 
int main() {
    cin >> n >> k;
    int a, b, ans = 1; k--;
 
    while (cin >> a) {
        if (!a) { break; continue; }
        cin >> b;
        a--; b--;
        w[b][a] = 1;
    }
 
    dfs(k);
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) ans = 0;
    }
    cout << (ans ? "Yes" : "No");
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@Zivaka 0 / 0 / 0 Регистрация: 02.11.2014 Сообщений: 21

	Для любителей графов 30.03.2015, 18:59. Показов 4886. Ответов 4 Метки нет (Все метки) Иван Иванович любит ходить на скачки, надеясь на них заработать кругленькую сумму. Ему приглянулась лошадь с номером K, и он решил проверить, сможет ли она выиграть у всех остальных лошадей. Иван Иванович раздобыл информацию, в которой для некоторых пар лошадей сообщается, какая из этих лошадей быстрее. Также он узнал, что у всех лошадей разные скорости. Требуется написать программу, которая поможет Ивану Ивановичу точно определить может ли выиграть выбранная им лошадь. Входной текстовый файл содержит в первой строке два целых числа N (1 <= N <= 100) и K (1 <= K <= N), где N - количество лошадей, принимающих участие в скачках, K - номер лошади, на которую хочет сделать ставку Иван Иванович. Следующие строки содержат по два числа X и Y (1 <= X, Y <= N), обозначающие, что лошадь с номером X быстрее лошади с номером Y. Пары X и Y не повторяются. Набор данных завершается строкой, содержащей единственный ноль. Эту строку обрабатывать не надо. Гарантируется, что информация, раздобытая Иваном Ивановичем, корректна. Выходной текстовый файл должен содержать слово "Yes" без кавычек, если Иван Иванович уверен в своем выигрыше. В противном случае выведите "No" без кавычек. Пример: 1 тест 5 5 1 2 2 3 3 4 5 1 0 Yes 2 тест 4 2 2 3 4 1 0 No 3 тест 3 1 1 2 3 2 0 No Помогите придумать, как использовать графы. 0

@dmitrydm 0 / 0 / 0 Регистрация: 30.03.2015 Сообщений: 8
	30.03.2015, 23:35
	задали именно эту задачу! присоединяюсь и прошу помочь! 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	31.03.2015, 00:40
	Сообщение было отмечено Zivaka как решение Решение Расскажу идею. Пусть лошадь А быстрее лошади Б. Тогда для графа будет существовать дуга от вершины А к вершине Б. Граф представляется в виде квадратной несимметричной матрицы (0 - нет дуги, 1 - есть дуга, диагональ - 0). Если ставка идет на лошадь Х, то нам нужно проверить, возможно ли посетить из вершины Х все остальные вершины. Если это возможно, то тогда лошадь Х самая быстрая, иначе непонятно, то бишь "No". 1

Для любителей графов

Решение