Подсчет компонентов сильной связности

@Akim111111 · Регистрация: 13.11.2023

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

Доброго времени суток, пытаюсь написать программу, которая на вход получает количество точек в графе(n) и количество ребер в нем (m), а в следующих m строках описывается ребра((пример 1 2) значит из точки 1 идет направленное ребро в точку 2). Я пытаюсь выполнить эту программу через dfs, то есть сначала прохожусь dfs по всем точкам и записываю их в вектор, потом записываю их в обратном порядке, затем строю инвертированный граф (направление ребер меняется), и начинаю использовать dfs на инвертированном графе, но не в прямом порядке как в первом случае, а беру вершины из созданного до этого списка, по сути то, сколько в этот раз запустится dfs и будет количеством компонентов сильной связности. Предоставляю свой код:

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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<bool> visited1;
vector<bool> visited2;
vector<int> result;
vector<int> between_stack;
vector<int> between_stack2;
 
void dfs1(int u, vector<vector<int>>& G) {
    visited1[u] = true;
 
    for (int v : G[u]) {
        if (!visited1[v]) {
            dfs1(v, G);
        }
        between_stack.push_back(u);
    }
 
 
}
 
void dfs2(int u, vector<vector<int>>& H) {
    visited2[u] = true;
 
    for (int v : H[u]) {
        if (!visited2[v]) {
            dfs2(v, H);
        }
        result.push_back(u);
    }
 
 
}
 
int main() {
    vector<vector<int>> G, H;
    int n, m;
    cin >> n >> m;
    int count = 0;
    G.resize(n);
    H.resize(n);
    between_stack2.resize(n);
    between_stack.resize(n);
 
    visited1.resize(n, false); // Исправлено
    visited2.resize(n, false); // Исправлено
 
    for (int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        G[v-1].push_back(u-1);
        H[u-1].push_back(v-1);
    }
 
    for (int u = 0; u < n; u++) {
        if (!visited1[u]) {
            dfs1(u, G);
        }
    }
 
    for (int i = 0; i < between_stack.size(); i++) {
        between_stack2[i] = between_stack[between_stack.size() - 1 - i];
    }
 
    for (int u : between_stack2) {
        if (!visited2[u]) {
            dfs2(u, H);
            count++;
        }
    }
 
    cout << count;
    return 0;
}

На входных данных:
4 2
1 2
3 1
Выводит: 2
Это правильно
Но на других наборах выдает ошибку или неправильный ответ. Помогите найти в чем ошибки или недочеты, а то все воскресенье просидел, та и не решил.
Есть еще предположение, что я не правильно понял текст задачи, если будет желание почтить, то прикрепляю условие:
Четыре гнома Брисинга создали ожерелье невероятной красоты и назвали его Брисингамен. Ожерелье состояло из NN бусин и было создано таким образом, что любые две бусины могли быть связаны друг с другом несколькими нитками, а также любая бусина может быть оплетена ниткой (по сути связана с самой собой).

Однажды богиня любви Фрейя гуляла по лесу и набрела на пещеру, где эти четыре гнома сидели и любовались своим творением. Увидев столь невероятное украшение, девушка тотчас же захотела заполучить его. Но гномы согласились отдать его, только если Фрейя одарит каждого из них своим вниманием.

Спустя некоторое время, богиня вернулась в свой замок Фолькванг уже с ожерельем. Верховный бог Один, возлюбленный Фрейи, узнав о случившемся, разгневался и приказал Локи выкрасть Брисингамен. Ночью Локи, превратившись в блоху, пробрался в покои богини и сумел снять с неё украшение. Когда Локи убегал оттуда с Брисингаменом, Хеймдалль, страж "радужного моста" между миром людей и миром асов, увидел воришку, погнался за ним и схватился за ожерелье. Под натяжением часть ниток, скреплявших бусины, порвалась.

Локи и Хеймдалль решили восстановить украшение. Для этого им нужно понять, сколько фрагментов ожерелья всё ещё крепко связаны. Фрагмент ожерелья считается крепко связанным, если у каждой бусины во фрагменте есть бусина из этого же фрагмента, к которой она присоединена, либо она одна в этом фрагменте.

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

В первой строке два целых числа NN - количество бусин, MM - количество сохранившихся связей между бусинами (0≤N≤105,0≤M≤106)(0≤N≤105,0≤M≤106).

В следующих MM строках даны пары чисел (i,j)(i,j) описывающие связь между ii-той и jj-той бусиной (1≤i,j≤N)(1≤i,j≤N).

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

Выведите количество крепко связанных фрагментов ожерелья.

@TheCalligrapher · 19.02.2024, 04:50

Сообщение от Akim111111

В первой строке два целых числа NN - количество бусин, MM - количество сохранившихся связей между бусинами

Ничего не понял. Что такое NN и MM и как они связаны с N и M?

Сообщение от Akim111111

даны пары чисел (i,j)(i,j)

"Пары чисел"? Но это какие пары пар. Что такое (i,j)(i,j)?

Сообщение от Akim111111

описывающие связь между ii-той и jj-той бусиной

ii-той и jj-той???

Сообщение от Akim111111

Фрагмент ожерелья считается крепко связанным, если у каждой бусины во фрагменте есть бусина из этого же фрагмента, к которой она присоединена, либо она одна в этом фрагменте.

Ничего не понял. Это тавтология какая-то. Согласно этому определению, все фрагменты являются крепко связанными. Приведите пример НЕ крепко связанного фрагмента.

Также, я не вижу в этой задаче никаких намеков на ориентированность связей между бусинами, то есть на ориентированность графа. При этом в заголовке вы упоминаете "подсчет компонентов сильной связности". Но сильная связность - это понятие из области ориентированных графов. И в решении вы упоминаете смену направления ребер. Откуда тут вдруг взялись направления ребер?

Новые блоги и статьи Все статьи Все блоги /
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 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .