Задача на графы

@impelix · Регистрация: 07.10.2022

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

Задан ориентированный граф. Ребро идущее от вершины А к вершине Б означает, что А выиграл у Б в ксго. И А считает Б раком. Но если Б выиграл в ксго у C то Б и А считают C раком. Нужно составить команду в которой необходим 1 капитан. При этом никто из участников команды не должен считать капитана раком. Сами участник могут считать друг друга раками.
Ниже мой код

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <vector>
using namespace std;
 
vector <int> G[100010];
vector <int> Gt[100010];
vector<bool> used;
vector<int> order, component, minn;
int res[200000];
//int n, m, num = 1;
 
void top(int v) {
    used[v] = 1;
    for (int i = 0; i < G[v].size(); i++) {
        if (used[G[v][i]] == 0) {
            top(G[v][i]);
        }
    }
    order.push_back(v);
}
 
void dfs(int v) {
    used[v] = 1;
    component.push_back(v);
    for (int i = 0; i < Gt[v].size(); i++) {
        if (used[Gt[v][i]] == 0) {
            dfs(Gt[v][i]);
        }
    }
}
 
int main() {
    int n, m, num = 1, temp, count = 0;
    cin >> n >> m;
    int aa[n][n];
    int vhod[n];
    for (int tt = 0; tt < n; ++tt)
        G[tt].resize(n);
    while (m--) {
        int a, b, kk;
        cin >> a >> b >> kk;
        a--;
        b--;
        if (kk == 1)
        {
            G[a].push_back(b);
            Gt[b].push_back(a);
            aa[a][b] = 1;
        }
        else
        {
            G[b].push_back(a);
            Gt[a].push_back(b);
            aa[b][a] = 1;
        }
    }
    int tt;
    for (int x = 0; x < n; ++x){
        for (int y = 0; y  < n; ++y){
            tt += aa[y][x];
        }
        vhod[x] = tt;
        tt = 0;
    }
    used.assign(n, false);
 
    for (int i = 0; i < n; i++) {
        if (used[i] == 0) top(i);
    }
 
    used.assign(n, false);
 
    for (int i = 0; i < n; i++) {
        int v = order[n - 1 - i];
        if (used[v] == 0) {
            dfs(v);
            for (auto I = component.begin(); I != component.end(); I++)
                res[*I] = num;
            num++;
            int temp = 0;
            for(int y:component){
                for(int x: component){
                    temp += aa[x][y]; //y - строка, X - столбец
                }
                if(vhod[y] - temp == 0){
                    minn.push_back(component.size());
                }
                }
            }
           // minn.push_back(component.size());
        }
    int min = minn[0];
    for (int k = 0; k < minn.size(); ++k) {
        //cout << minn[k] << " ";
        if (minn[k] < min) {
            min = minn[k];
        }
    }
    cout << min << endl;
    cout << n - min + 1 << endl;
    return 0;
}

И также есть 4 теста

4 3
1 2 1
2 3 1
3 4 1
Вывод: 4
Тест 2
Ввод:
3 6
1 2 1
1 2 2
1 3 1
1 3 2
2 3 1
2 3 2

Вывод: 1

тест 3
Ввод:
9 19
1 6 1
1 7 1
2 6 1
2 7 1
1 2 1
1 2 2
3 6 1
3 7 1
4 6 1
4 7 1
5 6 1
5 7 1
3 4 1
4 5 1
5 3 1
6 8 1
6 9 1
7 8 1
7 9 1

Вывод: 8

Тест 4:
7 8
1 7 1
2 7 1
4 7 1
2 3 1
3 2 1
4 5 1
6 5 2
4 6 2

Вывод: 7

Добавлено через 4 минуты
первые 2 спокойно проходит, а вот на двух других ничего не получается. Я пытался реализовать идею с тем что мы ищем минимальную компоненту сильной связности с истоком. И берем капитан как этот исток, вычитаем размер компоненты так как в ней все считают капитана раком и прибавляем всех остальных.

Добавлено через 3 минуты

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <vector>
using namespace std;
 
vector <int> G[100010];
vector <int> Gt[100010];
vector<bool> used;
vector<int> order, component, minn;
int res[200000];
vector<int> all;
int aa[10000][10000];
int n, m, num = 1, temp, count = 0;
 
//int n, m, num = 1;
 
void top(int v) {
    used[v] = 1;
    for (int i = 0; i < G[v].size(); i++) {
        if (used[G[v][i]] == 0) {
            top(G[v][i]);
        }
    }
    order.push_back(v);
}
 
void dfs(int v) {
    used[v] = 1;
    component.push_back(v);
    for (int i = 0; i < Gt[v].size(); i++) {
        if (used[Gt[v][i]] == 0) {
            dfs(Gt[v][i]);
        }
    }
}
 
int main() {
    cin >> n >> m;
    // int vhod[100];
    for (int tt = 0; tt < n; ++tt)
        G[tt].resize(n);
    while (m--) {
        int a, b, kk;
        cin >> a >> b >> kk;
        a--;
        b--;
        if (kk == 1)
        {
            G[a].push_back(b);
            Gt[b].push_back(a);
            aa[a][b] = 1;
        }
        else
        {
            G[b].push_back(a);
            Gt[a].push_back(b);
            aa[b][a] = 1;
        }
    }
    int tt = 0;
    /*for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            tt += aa[y][x];
        }
        vhod[x] = tt;
        tt = 0;
    }*/
    used.assign(n, false);
 
    for (int i = 0; i < n; i++) {
        if (used[i] == 0) top(i);
    }
 
    used.assign(n, false);
 
    for (int i = 0; i < n; i++) {
        int v = order[n - 1 - i];
        if (used[v] == 0) {
            dfs(v);
            for (auto I = component.begin(); I != component.end(); I++)
                res[*I] = num;
            num++;
            int temp = 0;
            all.push_back(component.size());
            for (int y : component) {
                for (int x : component) {
                    temp += aa[x][y]; //y - строка, X - столбец
                }
                for (int x = 0; x < n; ++x) {
                    for (int y = 0; y < n; ++y) {
                        tt += aa[y][x];
                    }
 
                    if (tt - temp > 0) {
                        minn.push_back(component.size());
                    }
                }
            }
            // minn.push_back(component.size());
        }
        int min = 0;
        for (int k = 0; k < minn.size(); ++k) {
            //cout << minn[k] << " ";
            if (minn[k] > min) {
                min = minn[k];
            }
        }
        int min1 = 0;
        for (int k = 0; k < all.size(); ++k) {
            cout << minn[k] << " ";
            if (all[k] > min1) {
                min1 = all[k];
            }
        }
        cout << min << " " << min1 << endl;
        cout << n - min + 1 << endl;
        return 0;
    }
}

Второй вариант кода

@impelix · 13.11.2022, 09:09 **[ТС]**

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <vector>
using namespace std;
 
vector < vector<int> > g, gr;
vector<char> used;
vector<int> order, component, gg;
 
void dfs1(int v) {
    used[v] = true;
    for (size_t i = 0; i < g[v].size(); ++i)
        if (!used[g[v][i]])
            dfs1(g[v][i]);
    order.push_back(v);
}
 
void dfs2(int v) {
    used[v] = true;
    component.push_back(v);
    for (size_t i = 0; i < gr[v].size(); ++i)
        if (!used[gr[v][i]])
            dfs2(gr[v][i]);
}
 
int main() {
    int n, m, tt= 0, temp= 0, count = 1;
    cin >> n >> m;
    int aa[100][100];
    //for (int k = 0; k < n - 1; ++k) {
    g.resize(n);
    gr.resize(n);
    int vhod[9];
    while (m--) {
        int a, b, kk;
        cin >> a >> b >> kk;
        a--;
        b--;
        if (kk == 1)
        {
            g[a].push_back(b);
            gr[b].push_back(a);
            aa[a][b] = 1;
        }
        else
        {
            g[b].push_back(a);
            gr[a].push_back(b);
            aa[b][a] = 1;
        }
    }
 
    used.assign(n, false);
    for (int i = 0; i < n; ++i)
        if (!used[i])
            dfs1(i);
    used.assign(n, false);
    for (int i = 0; i < n; ++i) {
        int v = order[n - 1 - i];
        if (!used[v]) {
            dfs2(v);
            //for (int kk : component) 
            //  cout << kk << " ";
            //cout << "next comp ";
            //gg.push_back(component.size());
            //count++;
            for (int y : component) {
                for (int x : component) {
                    temp += aa[x][y]; //y - строка, X - столбец
                }
                for (int x  : component) {
                    for (int y = 0; y < n; ++y) {
                        tt += aa[x][y];
                        if (tt - temp == 0) {
                            //gg.pop_back();
                            //cout << component.size() << endl;
                            gg.push_back(component.size());
                            count++;
                            tt = 0;
                            temp = 0;
                        }
                        }
                        tt = 0;
                        temp = 0;
                    }
                }
            }
            // minn.push_back(component.size());
            component.clear();
        }
    int min = 1000;
    for (int k : gg) {
        //cout << k << " ";
        if (min > k) {
            min = k;
        }
    }
    //cout << min << endl;
    //if (min == 1) {
    //  min++;
    //}
    cout << n - min + 1;
}

Не заходит только третий тест теперь

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .