Форум программистов, компьютерный форум, киберфорум
Visual C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 20.09.2017
Сообщений: 17

Поиск мостов в графе.Алгоритм работает,но на больших данных получается висяк

06.02.2018, 21:12. Показов 940. Ответов 0
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<vector>
#include<iostream>
#include<map>
#include<fstream>
#include<algorithm>
using namespace std;
int edge = 1;
int timer;
int n;
vector<int> tin;
vector<int> fup;
vector<bool> used;
vector<vector<int>> mas;
map<vector<int>, int> start;для записи каким какое ребро было считано из файла
map<vector<int>, bool> q;//для проверки на мультиребра
map<int, int> points;
vector<int> result;
void v(int &s1, int &s2, int count)
{
    ifstream s("6.in");
    for (int z = 0; z < count; z++) {
        char* str = new char[100];
        s.getline(str, 100);
    }
    s >> s1; s >> s2;
    s.close();
}
void IS_BRIDGE(int s1, int s2)
{
    vector<int> temp(2);
    temp[0]=s1;
    temp[1]=s2;
    auto s = q.find(temp);
    if(s==q.cend())
    {
        swap(temp[0], temp[1]);
    }
    s = q.find(temp);
    if (s->second)
    {
        points.insert(pair<int, int>(s1, s2));
        auto fin = start.find(temp);
        result.push_back(fin->second);
        
    }
}
void dfs(int v, int p = -1) // poisk v glubinu
{
    used[v] = true;
    tin[v] = fup[v] = timer++;
    for (int i = 0; i < n; ++i)
    {
        if (mas[v][i] == 1)
        {
            int to = i;
            if (to == p)  continue;
            if (used[to]) fup[v] = std::min(fup[v], tin[to]);
            else
            {
                dfs(to, v);
                fup[v] = std::min(fup[v], fup[to]);
                if (fup[to] > tin[v])
                {
                    IS_BRIDGE(v + 1, to + 1);
                }
            }
        }
    }
}
 
void find_bridges() // poisk mostov
{
    timer = 0;
    for (int i = 0; i < n; ++i)
    {
        used[i] = false;
    }
    for (int i = 0; i < n; ++i)
    {
        if (!used[i])
            dfs(i);
    }
}
 
 
int main()
{
    ifstream s("6.in");
    int number_of_tops, number_of_edges;
    s >> number_of_tops; s >> number_of_edges;//Здесь я прости считываю с файла данные.Там в 1 строке кол-во вершин,во 2 кол-во ребер.В каждой следующей по 2 цифры, обозначающие начало и конец каждого ребра
    n = number_of_tops;
    s.close();
    mas.resize(number_of_tops);
    for (int i = 0; i < number_of_tops; i++)
    {
        mas[i].resize(number_of_tops);
    }
    int temp1 = 0, temp2 = 0;
    int count = 2;
    for (int i = 0; i < number_of_edges; i++)
    {
        v(temp1, temp2, count);
        count++;
        vector<int> temp(2);
        temp[0] = temp1;
        temp[1] = temp2;
        auto found = q.find(temp);
        if (found == q.end())
        {
            q.insert(pair<vector<int>, bool>(temp, true));
        }
        else
        {
            found->second = false;//проверка но  мультиребро
        }
        start.insert(pair<vector<int>, int>(temp, edge));
        edge++;
        mas[temp1 - 1][temp2 - 1] = 1; mas[temp2 - 1][temp1 - 1] = 1;
    }
    system("pause");
    tin.resize(number_of_tops);
    fup.resize(number_of_tops);
    used.resize(number_of_tops);
    find_bridges();
    cout << result.size() <<"       ";
    for (int i = 0; i<result.size(); i++)
    {
        cout << result[i]<<" ";
    }
    cout <<endl<< points.size()*2 << endl;
    for (auto i = points.begin(); i != points.end(); i++)
    {
        cout << i->first <<" "<< i->second << endl;
    }
    system("pause");
    return 0;
}
До 10 вершин все нормально.Но есть тест, там 10000 вершин.Если я правильно понимаю,ступар начинается при заполнении матрицы смежности.Подскажи,как оптимизировать?
Пример:
6
7
1 2
2 3
1 3
3 4
4 5
5 6
4 6
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
06.02.2018, 21:12
Ответы с готовыми решениями:

Поиск мостов в графе
Доброй ночи,задача состоит в отыскании мостов в графе. Много где есть в свободном доступе алгоритм примерно такого рода: ...

Поиск мостов в графе
дано условие: найти мосты в графе. порылся в книжках и соорудил вот это. vector&lt;int&gt; g; bool used; int timer, tin, fup; ...

Нахождение мостов в графе.
Дан граф.Найти все мосты.Мост-ребро при удалении которого создается компонента связности(проще говоря если удалить такое ребро,то...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
06.02.2018, 21:12
Помогаю со студенческими работами здесь

Количество мостов в неориентированном графе
Здравствуйте, я хотел бы посчитать количество мостов,с помощью нахождения компонент реберной двусвязности. Но сколько не смотрел сайтов, я...

Реализация поиска мостов на графе
Подскажите, в чем проблема. Вроде весь код написан верно, но ничего не считает в итоге. У меня есть неориентированный граф, который я задаю...

Алгоритм Дейкстры (поиск кратчайшего пути в графе)
Доброго времени суток! Пытаюсь разобраться в алгоритме Дейкстры по книжке &quot;Грокаем алгоритмы&quot;, статье на Википедии и видеоуроках....

Поиск кратчайших путей в графе. Алгоритм Данцига
Есть ли у кого-то хороший источник с информацией по данному методу/алгоритму? Желательно с примерами. Буду очень благодарен

Алгоритм Брона-Кербоша или поиск клик в графе
Собственно озадачился решением одной задачи: имеется матрица весов взвешенного ориентированного графа: {0, 6, 0, 5, 4}, {0, 0, 4, 0,...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .
Команды формы и диалоговое окно
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при создании или изменении элементов справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru