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

[C++] Компоненты связанности :( - C++

Восстановить пароль Регистрация
 
Kill100
 Аватар для Kill100
356 / 245 / 32
Регистрация: 11.12.2010
Сообщений: 1,058
Завершенные тесты: 1
15.03.2011, 18:56     [C++] Компоненты связанности :( #1
Помогите решть(
уже 4 день мучаюсь (
Дано:
n- количество вершин графа.
Ag матрица смежности n*n
Найти матрицу сильной связанности..

Определить количество компонент сильной связности, и матрици смежности этих компонент..

С первой частью задания проблемы особой нету а вот со второй...

Добавлено через 11 минут
http://www.cyberforum.ru/cgi-bin/latex.cgi?{T}_{g}={A}^{1}+{A}^{2}+{A}^{3}+...+{A}^{n-1}
http://www.cyberforum.ru/cgi-bin/latex.cgi?{Q}_{g}={{T}_{g}}^{t}
http://www.cyberforum.ru/cgi-bin/latex.cgi?S={Q}_{g}*{T}_{g}

Добавлено через 49 секунд
Это то что нашёл в лекциях...
S - матрица сильной связанности...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
15.03.2011, 19:00     [C++] Компоненты связанности :( #2
вот все детально расписано + код
Kill100
 Аватар для Kill100
356 / 245 / 32
Регистрация: 11.12.2010
Сообщений: 1,058
Завершенные тесты: 1
15.03.2011, 19:20  [ТС]     [C++] Компоненты связанности :( #3
Цитата Сообщение от Mayonez Посмотреть сообщение
вот все детально расписано + код
Код не работает и я его не понял

Вот мои наработки
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
#include<conio.h>
#include<iostream.h>
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** prozv_m(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 main(){
        cout<<"Vvedite kol vo vershin \n";
cin>>n; 
cout<<"Vvedite matricu Ag \n";
int** Ag=enter();
//возвожу в степень
int **df=prozv_m(Ag,Ag);
int **dff=Ag;
if(n>2){
                for(int i=0; i<n-1; i++)
                    for (int j=0;j<n;j++)
                        for (int k=0;k<n;k++){
                
                       dff[j][k]+=df[j][k];}
                df=prozv_m(df,Ag);
 
                };
int **S;
    for (int i=0;i<n;i++)
    for (int j=0;j<n;j++){
S[i][j]=dff[j][i]*dff[i][j];
 
 
}
 
 
 
return 0 ;
}
А дальше не знаю что делать да и этот код по ходу с багами
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
15.03.2011, 19:41     [C++] Компоненты связанности :( #4
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
#include <iostream>
#include <vector>
 
using namespace std;
//нужно где-то еще заполнить это
vector < vector<int> > g, gr;
//g- сам граф а gr - транспонированый
vector<char> 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]);
}
 
void print()
{
   for (int i = 0; i < component.size(); i++)
      cout << component[i] << " ";
   cout << endl;
}
 
int main() {
   locale::global(locale(""));
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cout << "Введите следующее ребро, тоесть две вершины по очереди: ";
        cin >> a >> b;
        g[a].push_back (b);
        gr[b].push_back (a);
    }
 
    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);
            print();
            component.clear();
        }
    }
 
    return 0;
}
Нужно только заполнить сам граф и его транспонированый
Kill100
 Аватар для Kill100
356 / 245 / 32
Регистрация: 11.12.2010
Сообщений: 1,058
Завершенные тесты: 1
15.03.2011, 20:18  [ТС]     [C++] Компоненты связанности :( #5
Так не работает ((
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
#include <iostream>
#include <vector>
 
using namespace std;
         int 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;        
}
//Г*ГіГ¦Г*Г® ãäå-ГІГ® ГҐГ№ГҐ Г§Г*ïîëГ*ГЁГІГј ГЅГІГ®
vector < vector<int> > g, gr;
//g- Г±Г*Г¬ ГЈГ°Г*Гґ Г* gr - ГІГ°Г*Г*Г±ГЇГ®Г*èðîâГ*Г*ûé
vector<char> 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]);
}
 
void print()
{
   for (int i = 0; i < component.size(); i++)
      cout << component[i] << " ";
   cout << endl;
}
 
 
 
int main() {
   locale::global(locale(""));
 
        cin >> n;
        g=enter();
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        gr[i][j]=g[j][i];
        
        for (int i = 0; i < n; i++) {
                int a, b;
                cout << "Ââåäèòå ñëåäóþùåå ðåáðî, òîåñòü äâå âåðøèГ*Г» ГЇГ® î÷åðåäè: ";
                cin >> a >> b;
                g[a].push_back (b);
                gr[b].push_back (a);
        }
 
        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);
                        print();
                        component.clear();
                }
        }
 
        return 0;
}
Kill100
 Аватар для Kill100
356 / 245 / 32
Регистрация: 11.12.2010
Сообщений: 1,058
Завершенные тесты: 1
17.03.2011, 13:34  [ТС]     [C++] Компоненты связанности :( #6
Бл не как не получается ((
Yandex
Объявления
17.03.2011, 13:34     [C++] Компоненты связанности :(
Ответ Создать тему
Опции темы

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