192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 935
1

Задача на теорию графов

19.08.2017, 10:06. Показов 10581. Ответов 10
Метки нет (Все метки)

Светофорчики
В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

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

Во входном файле INPUT.TXT записано два числа N и M (0 < N ≤ 100, 0 ≤ M ≤ N*(N-1)/2). В следующих M строках записаны по два числа i и j (1 ≤ i,j ≤ N), которые означают, что перекрестки i и j соединены тоннелем. Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

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

В выходной файл OUTPUT.TXT вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

HTML5
1
2
3
4
5
6
7
8
9
10
11
12
INPUT.TXT                      OUTPUT.TXT
7 10                          3 3 2 2 5 2 3
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3
Раньше не решал задачи на графы. Объясните пожалуйста решение, как эта задача решается с помощью графов
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.08.2017, 10:06
Ответы с готовыми решениями:

Задача на теорию автоматов
Условие во вложение. Не совсем понимаю алгоритм. Есть какие-нибудь идеи?

Задача на теорию чисел
Торт от Толи Толя на день рождения собирается угостить друзей тортом. Известно, что на дне...

Задача на программирование и теорию вероятностей
Требуется написать фрагмент тела функции, который присваивает переменным a, b и c такие случайные...

Транспортная задача теорией графов
Возникла необходимость написать решение транспортной задачи, используя теорию графов. Одна поиски...

10
353 / 134 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
19.08.2017, 11:07 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
 
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 0; i < n; i++) {
        cout << v[i].size() << " ";
    }
    return 0;
}
Можно не хранить вершины. А просто v[a]++; v[b]++;
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 935
19.08.2017, 13:08  [ТС] 3
А можно взять массив двумерный размером mas[N][N] и mas[a][b] делать +1?

Добавлено через 54 минуты
А почему M <= n * (n - 1) / 2, разве n / 2 не будет?
0
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
19.08.2017, 16:14 4
Цитата Сообщение от no swear Посмотреть сообщение
А можно взять массив двумерный размером mas[N][N] и mas[a][b] делать +1?
Можно. Но когда вершин очень много это по памяти слишком затратно.
Цитата Сообщение от no swear Посмотреть сообщение
А почему M <= n * (n - 1) / 2, разве n / 2 не будет?
Представьте что в графе между каждыми двумя вершинами есть ребро. Сколько ребер?
Есть ребро 1-2, 1-3, ... 1-n; 2-1, 2-3, ... 2-n В общем для каждой из n вершин n-1 ребро, но мы не учли то что 1-2 и 2-1 это одинаковое ребро, потому n * (n-1) / 2
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 935
19.08.2017, 19:30  [ТС] 5
Как вообще можно представить эту задачу? Ну вот у нас есть 7 перекрестков как в примере и 10 тоннелей, дальше N строк с числами какой перекресток(вершина) с каким перекрестком(вершиной) связан. Дальше что делать? Я пробовал по своему методу написать но не получилось а смысл кода выше я не очень понял
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
20.08.2017, 18:38 6
Лучший ответ Сообщение было отмечено no swear как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
 
 
int main() {
    int N;
    std::cin >> N;
    std::vector<int> vec(N);
 
    int M;
    std::cin >> M;
    for (int i = 0; i < 2 * M; ++i) {
        int node;
        std::cin >> node;
        ++vec[node - 1];
    }
 
    for (int i = 0; i < N; i++)
        std::cout << vec[i] << " ";
    std::cout << std::endl;
}
2
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 935
20.08.2017, 19:53  [ТС] 7
Цитата Сообщение от avgoor Посмотреть сообщение
C++
1
++vec[node - 1];
Почему вы вводимое число уменьшаете на 1?
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
20.08.2017, 19:57 8
no swear, потому, что номер перекрестка начинается с 1, а индекс вектора с 0.
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 935
21.08.2017, 07:00  [ТС] 9
А если бы задавались не по два перекрестка а по три(cin >> a >> b >> c)?
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
21.08.2017, 19:08 10
no swear, тогда это был бы не граф, а хзч. Но, в этом случае вместо 2 * M в условии цикла было бы... догадайтесь.
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 935
21.08.2017, 20:06  [ТС] 11
Ну если мы вводим как в последнем коде через одну переменную (cin >> node) то явно будет 3 * M

Спасибо большое за то что помогли разобраться с этой задачей, ОЧЕНЬ вам благодарен
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.08.2017, 20:06
Помогаю со студенческими работами здесь

Теория графов. Задача Обрати меня!
Мальчик Вася очень любит разворачивать ориентированные графы. Помогите ему в этом. Входные...

Теорие графов. Композиция двух неор. графов.
Здравствуйте. Прошу помощи уже здесь :| (old topic)... Прошу помочь с составлением алгоритма...

Кто понимает теорию графов? Для вас может эта задача разминка для мозга
Не понимаю как понять это.. Удалил вложение

Как можно практически применить теорию случайных графов?
Не даёт мне спать один вопрос : как на практике можно применить теорию случайных графов? В Unity3D...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru