Форум программистов, компьютерный форум CyberForum.ru

Графы и компоненты связности в них - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Дмитрий6
0 / 0 / 0
Регистрация: 22.04.2013
Сообщений: 9
22.04.2013, 17:35     Графы и компоненты связности в них #1
Здравствуйте уважаемые программисты вот есть такая задачка Реализовать алгоритм разбиение графа на компоненты сильной связности.

В первой строке заданы два числа, разделенных пробелом n, m(1≤n≤1000,0≤m≤n(n-1)) количество вершин и количество ребер в графе соответственно. В последующих m строках идут пары чисел x,y(1≤x,y≤n), означающих, что из вершины x можно попасть в вершину y.

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

Вот то, что у меня получилось программа выводит количество компонент сильной связности а вот как сделать чтобы она выводила количество вершин в данной компоненте и список этих вершин у меня не получается помогите дописать программу

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
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> g[20000], gr[20000];
vector<bool> used;
vector<int> order, component;
 
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,i,a,b,res[20000],num=1,a1=0;
    cin>>n>>m;
    for (i=0;i<m;i++) {
        cin>>a>>b;
        g[a-1].push_back (b-1);
        gr[b-1].push_back (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);
            vector<int>::iterator I;
            for(I=component.begin(); I!=component.end(); I++)
                res[*I]=num;        
            num++;
            component.clear();
        }
    }
    cout<<num-1<<endl;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2013, 17:35     Графы и компоненты связности в них
Посмотрите здесь:

C++ не компилируется задание: компонент связности графа - кто разберется
C++ Упорядочить компоненты вектора так, чтобы сначала размещались все отрицательные компоненты, а затем положительные
целое положительное К, за которым следуют К вещественных чисел. Определите, сколько из них отрицательных. Найдите наибольшее из них. C++
C++ целое положительное К, за которым следуют К вещественных чисел. Определите, сколько из них отрицательных. Найдите наибольшее из них
C++ Найти компоненты связности
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
22.04.2013, 18:52     Графы и компоненты связности в них #2
вы б попробовали разобраться в алгоритме, а не тупо копипастить e-maxx. сразу бы проблемы решились.
Дмитрий6
0 / 0 / 0
Регистрация: 22.04.2013
Сообщений: 9
22.04.2013, 20:42  [ТС]     Графы и компоненты связности в них #3
Так алгоритм то несложный в теории я знаю как это сделать дело в реализации в ней я и прошу помочь
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
22.04.2013, 20:44     Графы и компоненты связности в них #4
да? опишите алгоритм.
Дмитрий6
0 / 0 / 0
Регистрация: 22.04.2013
Сообщений: 9
22.04.2013, 20:55  [ТС]     Графы и компоненты связности в них #5
Ну я хотел сделать через множества 1 множество-это множество вершин, а второе-это множество компонент если данная вершина принадлежит компоненте, то увеличиваем счетчик на 1 и так для каждой вершины
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
22.04.2013, 20:57     Графы и компоненты связности в них #6
а код с другим алгоритмом вы выложили, чтобы работоспособность сайта проверить?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2013, 21:00     Графы и компоненты связности в них
Еще ссылки по теме:

Компоненты связности графа поиском в глубину C++
C++ В неориентированном графе посчитать количество компонент связности
Ошибка в поиске компоненты сильной связности (графы) C++

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

Или воспользуйтесь поиском по форуму:
Дмитрий6
0 / 0 / 0
Регистрация: 22.04.2013
Сообщений: 9
22.04.2013, 21:00  [ТС]     Графы и компоненты связности в них #7
да нет он кстати не полностью скопирован я там некоторые шаги дописывал
Yandex
Объявления
22.04.2013, 21:00     Графы и компоненты связности в них
Ответ Создать тему
Опции темы

Текущее время: 15:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru