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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Создать массив из 7 чисел, и определить кол-во цифр в каждом числе, без знаков + и - а так же , и т.д http://www.cyberforum.ru/cpp-beginners/thread845306.html
#include <iostream> #include <conio.h> using namespace std; int main() { unsigned result; string s1 = "+112120"; cout << "S1: " << s1 << endl; string s2 = "-21215"; cout << "S1: " << s2 << endl;
C++ Определить все подпоследовательности.С++ Здравствуйте, будьте добры,обьясните,как это реализовать? Необходимо определить все подпоследовательности,данные считываются с файла. (Необходимо реализовать в Visual Studio) Заранее благодарна. http://www.cyberforum.ru/cpp-beginners/thread845301.html
Повторить каждый символ, который отличается от заданного символа C++
в строке символов типа char Написать нужно со struct (без string), просто не понимаю, куда и зачем там структуры, и если не сложно какой-нибудь простенький примерчик реализации чего-нибудь похожего со struct Добавлено через 1 час 8 минут up/
C++ Безопасный массив
Здравствуйте,помогите пожалуйста,как подстроить данную программу под безопасный массив (контроль границ).Своими силами не получается.Заранее благодарю. #include <iostream> #include <cmath> using namespace std; class samp {double a; public: double put_a (double n) {a=n;} double get_a() {if(a>10)
C++ Окончание слова - xyz (СИ) http://www.cyberforum.ru/cpp-beginners/thread845283.html
Приветствую. Нужно сделать программу, которая бы выводила на экран слова, окончания которых - xyz. Программу нужно сделать при помощи массива строк, то есть вот инициализация и вывод на экран: #include <stdio.h> #include <string.h> int main (void) { int n, i, j; printf ("Enter n\n"); scanf ("%d", &n); char str;
C++ Создать следующую программу: при наведении указателя мыши на кнопку ее координаты изменяются произвольным образом в пределах формы (кнопка убегает Создать следующую программу: при наведении указателя мыши на кнопку ее координаты изменяются произвольным образом в пределах формы (кнопка убегает от указателя мыши) подробнее

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

В первой строке заданы два числа, разделенных пробелом 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 01:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru