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

Компоненты связанности графа - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ перестала работать программа http://www.cyberforum.ru/cpp-beginners/thread277266.html
вот задание: http://s009.***********/i307/1104/83/3ca134771e20.jpg написал программу, все проверил со всеми возможными вариантами - работало. Через неделю смотрю и с делением на 0 не работает,...
C++ Курсор Как получить символ в определённой позиции курсора в консоле? Допустим по среди экрана выведено HELLO WORLD! и надо получить допустим символ, который идёт после буквы W :) с помощью курсора в... http://www.cyberforum.ru/cpp-beginners/thread277234.html
Калькулятор(улучшенный) C++
Здравствуйте.Столкнулся с такой проблемой: Надо написать калькулятор, который считает по введенной строке. Подскажите какие алгоритмы лучше использовать? Пробовал с помощью обратной польской...
немогу разобратся с kbhit() C++
научите как kbhit() юзать? borland 3.1 если на пробел нажимаю(32) вроде нормально выполняет.. а если на кнопку "d" (100) то пару раз выполняет и выходит из программы хотя вроде не должен!!...
C++ прекращение работы программы http://www.cyberforum.ru/cpp-beginners/thread277176.html
int main(){ int i; cin>>i; cout<<i; if(i==5) cout<<"i="<<i<<endl; else (как тут прекратить программу просто что бы ничего не выводил)} return 0;
C++ Работа со строкой Помогите плз, задача такова: нужно прочитать из файла строку символов. Заменить в этой строке последовательности одинаковых символов (не пробелов) на число, соответствующее их количеству и один этот... подробнее

Показать сообщение отдельно
Kill100
405 / 271 / 37
Регистрация: 11.12.2010
Сообщений: 1,155
Завершенные тесты: 1

Компоненты связанности графа - C++

16.04.2011, 00:06. Просмотров 892. Ответов 0
Метки (Все метки)

[C++] Компоненты связанности графа
Необходимо найти матрицу сильной связанности.
Количество компонент связанности и вывести их на экран..
Половину сделал а вот со второй проблемы (
Не как не могу понять как искать сами компоненты и как их выводить..
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<conio.h> 
#include<iostream.h> 
#include <windows.h>
#include<iomanip.h>
//еще 1 попытка реализовать русский текст в консольке        
char NEWT[256];
char*RUS(char*TEXT) {
CharToOem(TEXT,NEWT);
return NEWT;}
 
int n; 
//Печать матрици 
void print(int**a){ 
      for (int i=0; i<n; i++) 
      { 
          for (int j=0; j<n; j++) 
          cout<<a[i][j]<<" "; 
          cout<<"\n";}; 
} 
//Ввод матриц клавы 
int** enter(){ 
 
int **a=new int*[n]; 
     for (int i=0; i<n;i++){ 
      a[i]=new int [n];}; 
 
for (int i=0; i<n; i++) 
      { 
          for (int j=0; j<n; j++) 
         cin>>a[i][j]; 
        } ; 
return a; 
} 
 
 
//умножение матрицы на матрицу по матричному правилу
int** ymnoz(int **a,int**b){ 
 
int **c=new int*[n]; 
     for (int i=0; i<n;i++){ 
      c[i]=new int [n];}; 
 for (int i=0;i<n;i++){ 
      for (int j=0;j<n;j++){ 
     c[i][j]=0 
     ;};} 
for (int i=0;i<n;i++){ 
      for (int j=0;j<n;j++){ 
        for (int k=0;k<n;k++){
            c[i][j]+=a[i][k]*b[k][j]
            ;}
         ;}
      ;}; 
      
return c; 
}
 
//функция возведения в степень и сложения
int** pow(int **Ag){
//создаю матрицу C 
int **c=new int*[n]; 
     for (int i=0; i<n;i++){ 
      c[i]=new int [n];}; 
//делаю матрицу единичной для последующего умножения на Ag
 for (int i=0;i<n;i++){ 
      for (int j=0;j<n;j++){ 
     c[i][j]=0;
     c[i][i]=1
     ;};} 
//Создаю матрицу Z в которой будет хранится E+Ag^1+Ag2+Ag^n
int **z=new int*[n]; 
     for (int i=0; i<n;i++){ 
      z[i]=new int [n];}; 
 for (int i=0;i<n;i++){ 
      for (int j=0;j<n;j++){ 
     z[i][j]=0;
     z[i][i]=1
     ;};}      
//Выполняю возведение в степень и сложение     
for(int i=0; i<n; i++){
c=ymnoz(Ag,c);
for(int k=0; k<n; k++)
for(int j=0; j<n; j++)
z[k][j]+=c[k][j];
};
return z;
}
 
//Создаём матрицу Tg
int** Matr_Tg (int**K){
int **Tg=new int*[n]; 
     for (int i=0; i<n;i++){ 
      Tg[i]=new int [n];}; 
//если  Ki,j>0 то пишем 1 иначе 0     
for(int i=0; i<n;i++)
for(int j=0; j<n;j++){
if(K[i][j]>0){
              Tg[i][j]=1;
              }else
              {
             Tg[i][j]=0;    
              };};
return Tg;//возвращаю матрицу Tg
}
 
//функция нахождения матрицы сильной связанности 
int** Matr_Sg(int** Tg){
    //Создаю матрицу Sg
int** Sg=new int*[n]; 
     for (int i=0; i<n;i++){ 
      Sg[i]=new int [n];}; 
//поэлементно умножаю Tg на Транспонированную(Конт достижимости)        
for(int i=0; i<n;i++)
for(int j=0; j<n;j++)
{     
Sg[i][j]=Tg[i][j]*Tg[j][i];
    };    
return Sg;//Возвращаю получившуюся матрицу Sg
}
 
 
int main(){ 
cout<<RUS("Введите количество вершин \n"); 
cin>>n; 
cout<<RUS("Введите матрицу Ag \n"); 
int** Ag=enter(); 
//возвожу в степень и складываю 
int** c= pow(Ag);//сумма возведенных в степень матриц будет хранится тут
cout<<RUS("Матрица Tg \n"); 
print(Matr_Tg(c));
cout<<RUS("Матрица Sg - сильной связанности \n"); 
int** Sg=Matr_Sg(Matr_Tg(c));//Матрица Ып сильной связаности
print(Sg);
system("pause");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru