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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Дмитрий6
0 / 0 / 0
Регистрация: 22.04.2013
Сообщений: 9
#1

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

22.04.2013, 17:35. Просмотров 1932. Ответов 6
Метки нет (Все метки)

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

В первой строке заданы два числа, разделенных пробелом 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++
#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;string&gt; #include &lt;algorithm&gt; using namespace std; void search_depth(int v,...

Компоненты связности графа поиском в глубину - C++
Доброго времени суток милые форумчане!!! Очень нужна ваша помощь, сама справиться не в силах. Нужно посчитать количестко компонент...

Компоненты связности, мосты, точки сочленения - C++
Всем привет! Какими способами можно решить эту задачу? Дано прямоугольное черно-белое изображение размера N x M, которое содержит только...

Упорядочить компоненты вектора так, чтобы сначала размещались все отрицательные компоненты, а затем положительные - C++
заранее спасибо! кто поможет мне с задачей Дан вектор Х(а1,а2...аn)(n=100) упорядочить компоненты вектора так, чтобы сначала размещались...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
22.04.2013, 18:52 #2
вы б попробовали разобраться в алгоритме, а не тупо копипастить e-maxx. сразу бы проблемы решились.
Дмитрий6
0 / 0 / 0
Регистрация: 22.04.2013
Сообщений: 9
22.04.2013, 20:42  [ТС] #3
Так алгоритм то несложный в теории я знаю как это сделать дело в реализации в ней я и прошу помочь
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
22.04.2013, 20:44 #4
да? опишите алгоритм.
Дмитрий6
0 / 0 / 0
Регистрация: 22.04.2013
Сообщений: 9
22.04.2013, 20:55  [ТС] #5
Ну я хотел сделать через множества 1 множество-это множество вершин, а второе-это множество компонент если данная вершина принадлежит компоненте, то увеличиваем счетчик на 1 и так для каждой вершины
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
22.04.2013, 20:57 #6
а код с другим алгоритмом вы выложили, чтобы работоспособность сайта проверить?
Дмитрий6
0 / 0 / 0
Регистрация: 22.04.2013
Сообщений: 9
22.04.2013, 21:00  [ТС] #7
да нет он кстати не полностью скопирован я там некоторые шаги дописывал
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2013, 21:00
Привет! Вот еще темы с ответами:

В неориентированном графе посчитать количество компонент связности - C++
2. Компоненты связности В неориентированном графе посчитать количество компонент связности. В графе нет петель и кратных ребер. Формат...

целое положительное К, за которым следуют К вещественных чисел. Определите, сколько из них отрицательных. Найдите наибольшее из них - C++
Исходные данные : целое положительное К, за которым следуют К вещественных чисел. Определите, сколько из них отрицательных. Найдите...

целое положительное К, за которым следуют К вещественных чисел. Определите, сколько из них отрицательных. Найдите наибольшее из них. - C++
Исходные данные : целое положительное К, за которым следуют К вещественных чисел. Определите, сколько из них отрицательных. Найдите...

Как вручную ввести полные имена файлов что бы потом считать/записать информацию с них/на них? - C++
Надо открывать/закрывать файлы в программе для работы с ними. Файлы текстовые (не части проекта). Так вот. Как это сделать в коде я знаю...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.04.2013, 21:00
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru