1

Тема: Прошу переформулювати умову задачі на мові (термінології) графів.

Всього в чемпіонаті є n гравців. Для деяких пар гравців відомо хто з них може виграти в іншого. Гравець називається незручним, якщо не існує такого гравця, який точно може перемогти його. Тренер Баріка вирішив знайти всіх незручних для Баріка гравців. Виведіть їх у порядку не спадання номерів.
Вхідні дані
В першому рядку вхідного файлу містяться 2 цілі числа n і m — кількість гравців, і кількість пар гравців, для яких відомо, хто з них кого може перемогти. В наступних m рядках містяться по 2 цілі числа u i v в кожному (1≤u,v≤n,u≠v), що означають, що гравець u може перемогти гравця v.
Вихідні дані
Виведіть в єдиному рядку номери всіх незручних гравців у порядку неспадання.
Приклад
Вхідні дані
4 5
1 2
2 3
1 3
4 2
4 3
Вихідні дані
1 4

2

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

Є така поширена біда: при розв'язанні проблеми люди намагаються самі знайти рішення (і це дуже правильно), звужують проблему до того, що видається їм правильним розв'язком, а потім питають оце вузьке питання на форумі. Біда ж у тому, що часто вони не усвідомлюють, що проблема не в тому, що вони питають, а в тому, що вони неправильно обрали спосіб вирішення, і ця вузька відповідь не дасть їм нічого для розв'язання початкової проблеми.
Ну от поясніть, нащо вам оце переформульовувати? Щоб навчитися таке робити? Тоді якщо ми переформулюємо, ви не навчитеся цьому. Щоб відмахатися від викладача? Пишіть заяву на виключення, відмахаєтеся від усіх викладачів одразу.

3

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

Головне в кожному завданні правильно перейти від преамбули до суті завдання. Якщо правильно сформулювати завдання на мові графів, то тоді буде очевидно, які алгоритми теорії графів використовувати.

4

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

Тай завдання я вже виконав сам, тільки по часу не проходять всі тести.

5

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

aassii написав:

Тай завдання я вже виконав сам, тільки по часу не проходять всі тести.

Код та тести в студію.. :)

6 Востаннє редагувалося aassii (03.03.2019 22:57:59)

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

#include <iostream>
using namespace std;
int main()
{
    long long M, N, i, u, v;
    cin >> N >> M;
    signed char **matrix = new signed char*[N];
    for (i = 0; i < N; ++i)
    {
        matrix[i] = new signed char[M];
        for (u = 0; u < M; ++u) matrix[i][u] = 0;
    }
    for (i = 0; i < M; ++i)
    {
        cin >> u >> v;
        matrix[u - 1][i] = 1;
        matrix[v - 1][i] = -1;
    }
    for (i = 0; i < N; ++i)
    {
        for (u = 0; u < M; ++u)
            if (matrix[i][u]==-1) break;
        if (u==M) {cout<<i+1<<" ";}
    }
    cout << endl;
    return 0;
}

7

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

Вхідні дані
4 5
1 2
2 3
1 3
4 2
4 3
Вихідні дані
1 4

8 Востаннє редагувалося koala (03.03.2019 23:14:31)

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

Теорія графів тут хіба що для загального розуміння, що відбувається, допоможе.
"Гравець називається незручним, якщо не існує такого гравця, який точно може перемогти його." - отже, якщо існує такий гравець, то гравець не є незручним.
1. Складаєте масив з N чисел від 1 до N.
2. В циклі до M читаєте u,v і в v-й елемент масиву (підказка: a[v-1], бо нумерація гравців від 1, а масиву від 0) записуєте 0 - цей гравець не може бути незручним. u взагалі нам не потрібно - яка різниця, хто може перемогти, все одно гравець перестає бути незручним.
3. Проходитеся по масиву і виводите всі ненульові номери.
4. PROFIT!

З точки зору теорії графів, у графі, де гравці - вершини, а відношення переможців - направлені ребра, наприклад, від переможця на переможеного, "незручними" будуть вершини без вхідних ребер.

long long - очевидно надмірне значення, вам знадобиться масив щонайменше з N елементів, а якщо N не влазить у 32 біти, тобто це щонайменше 2^31, то вам знадобиться явно надмірний об'єм пам'яті - 2^34Б = 17ГБ. Втім, можете трохи за допомогою vector<bool> зекономити, він зберігає 8 значень у байті.

Прихований текст
    std::cin>>n>>m;
    std::vector<bool> clumsy(n, true);
    while(m--) {
        std::cin>>v>>v;
        clumsy[v-1] = false;
    }

    for(size_t i=0;i<n;++i) {
        if(clumsy[i]) {
            std::cout<<i+1<<" ";
        }
    }
Подякували: aassii1

9

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

aassii, вам попередження за порушення п.1.1 Правил. Наступного разу буде бан. Повідомлення видалив.

10

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

koala, прошу вибачення, я не спеціально.

11

Re: Прошу переформулювати умову задачі на мові (термінології) графів.

Так я ж і не образився. Просто є Правила форуму.

Подякували: aassii1