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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.62
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
#1

Конденсация графа - C++

26.05.2012, 01:02. Просмотров 3054. Ответов 9
Метки нет (Все метки)

Найти число компонент сильной связности, вот
может быть кто-нибудь реализовывал нечто подобное?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2012, 01:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Конденсация графа (C++):

заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь - C++
Задание: заданно матрицу смежности простого графа. Построить каркас этого графа с использованием поиска вширь. Помогите написать...

Подобие графа - C++
Имеется примерно такой вот класс: class Room { private: string name; string story; vector <Room*> rooms; //указатели,...

Построение графа - C++
Вершины и ребра графа назовем его элементами. По графу G построить граф T(G), у которого в качестве вершин взяты элементы G, а две вершины...

построение графа - C++
Задача: "Задан граф дерево с корневой вершиной. Нужно, начиная с корневой вершины, обойти все концевые вершины (концевая вершина имеет...

Периферия графа - C++
Ребят, есть у кого код на нахождение периферии графа?

Построение графа - C++
Помогите пожалуйста написать программу вот задание:Построить копию заданного графа. граф произвольный на ваш выбор. Добавлено через...

9
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.05.2012, 01:44 #2
ссылку, на сайт, где задачу можно сдать, можете написать?
0
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
26.05.2012, 02:06  [ТС] #3
например вот http://www.e-olimp.com/problems/1947
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.05.2012, 03:20 #4
nicenice, это другая задача, хоть и близкая по теме. Я могу ее решить. Но тогда выложу код только этой задачи. Согласны?
0
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
26.05.2012, 11:41  [ТС] #5
Вы имеете ввиду ту задачу, которая на том сайте или мою?

Добавлено через 10 минут
ВОТ почти такой же только там надо ещё и для каждой вершины вывести номер компоненты сильной связности.

Добавлено через 1 минуту
Был бы очень рад, если бы вы решили бы задачу которая мне нужна, честно нету времени самому читать книги и разбираться.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.05.2012, 11:31 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от nicenice Посмотреть сообщение
ВОТ почти такой же только там надо ещё и для каждой вершины вывести номер компоненты сильной связности.
вот так проходит все тесты:
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
#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;
    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;
    for(i=0; i<n; i++)
        cout<<res[i]<<" ";
    return 0;
}
Цитата Сообщение от nicenice Посмотреть сообщение
честно нету времени самому читать книги и разбираться.
лучше найдите время, пригодится наверняка еще эта тема.
3
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
27.05.2012, 13:38  [ТС] #7
Спасибо большое. Можешь посоветовать достойную книгу, по которой можно хорошо научится программировать на Си++?
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.05.2012, 15:16 #8
Цитата Сообщение от nicenice Посмотреть сообщение
Можешь посоветовать достойную книгу, по которой можно хорошо научится программировать на Си++?
Я Ваш вопрос разобью на два вопроса (думаю для ответа на Ваш вопрос так будет правильнее):
- как научиться писать программы на Си++? Ответ можно найти здесь: Литература C++
- как научиться писать программы к олимпиадным задачам (Ваша задача как раз такая)? (Считаю что выбор языка здесь мало значит, больше значит опыт в решении таких задач, знание различных алгоритмов) Тут лучше всего и почитать литературу на такую тему, и решать задачи на соответствующих сайтах. Вот здесь почитайте: Олимпиадная подготовка
1
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
28.05.2012, 21:42  [ТС] #9
valeriikozlov, а что тут за алгоритм используется?
и что за push_back, откуда он там взялся? никаких деков вроде бы не подключается)
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
29.05.2012, 03:36 #10
Цитата Сообщение от nicenice Посмотреть сообщение
а что тут за алгоритм используется?
алгоритм Косарайю.

Цитата Сообщение от nicenice Посмотреть сообщение
и что за push_back, откуда он там взялся?

Не по теме:

книги точно Вам нужно почитать )


Цитата Сообщение от valeriikozlov Посмотреть сообщение
C++
1
vector<int> order;//так объявили вектор order
Цитата Сообщение от valeriikozlov Посмотреть сообщение
C++
1
order.push_back (v);// а так добавляем значение v в конец вектора order
1
29.05.2012, 03:36
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.05.2012, 03:36
Привет! Вот еще темы с ответами:

Визуализация графа - C++
Есть произвольный граф, состоящий из набора узлов и связей между ними. Узлы представляются прямоугольниками с известной шириной и высотой,...

Центр графа - C++
Дана матрица смежности. Найти максимальное расстояние в графе. Пол дня уже мучаюсь, искал в гугле, сам пытался, но ничего не...

K-связность неориентированного графа - C++
Ребят, третью неделю уже думаю, не могу решить. Нужно написать программу на с++, определяющую k-связность графа. Как я понял с...

Построение ориентированного графа - C++
Привет!) Покажу код, то что я делал. На выходе нету расстояний(стоимости). Как добавить расстояние на графе. #include...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

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