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

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

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

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

Добавлено через 1 минуту
Был бы очень рад, если бы вы решили бы задачу которая мне нужна, честно нету времени самому читать книги и разбираться.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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 Посмотреть сообщение
честно нету времени самому читать книги и разбираться.
лучше найдите время, пригодится наверняка еще эта тема.
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
27.05.2012, 13:38  [ТС]     Конденсация графа #7
Спасибо большое. Можешь посоветовать достойную книгу, по которой можно хорошо научится программировать на Си++?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.05.2012, 15:16     Конденсация графа #8
Цитата Сообщение от nicenice Посмотреть сообщение
Можешь посоветовать достойную книгу, по которой можно хорошо научится программировать на Си++?
Я Ваш вопрос разобью на два вопроса (думаю для ответа на Ваш вопрос так будет правильнее):
- как научиться писать программы на Си++? Ответ можно найти здесь: Литература C++
- как научиться писать программы к олимпиадным задачам (Ваша задача как раз такая)? (Считаю что выбор языка здесь мало значит, больше значит опыт в решении таких задач, знание различных алгоритмов) Тут лучше всего и почитать литературу на такую тему, и решать задачи на соответствующих сайтах. Вот здесь почитайте: Олимпиадная подготовка
nicenice
3 / 3 / 0
Регистрация: 22.11.2011
Сообщений: 168
28.05.2012, 21:42  [ТС]     Конденсация графа #9
valeriikozlov, а что тут за алгоритм используется?
и что за push_back, откуда он там взялся? никаких деков вроде бы не подключается)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.05.2012, 03:36     Конденсация графа
Еще ссылки по теме:

Хранения Графа в памяти C++
Обход в ширину графа C++
C++ Импорт графа из файла

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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
Yandex
Объявления
29.05.2012, 03:36     Конденсация графа
Ответ Создать тему
Опции темы

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