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

Непростая задача на графы. - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Моделирование фрактала в координатной плоскости http://www.cyberforum.ru/cpp-beginners/thread567037.html
Требуется написать программу, которая будет строить множество Мандельброта на координатной плоскости и выполнять некоторые функции. Цитирую текст задания: -------------------------------------------------------------------------------------------------------- Отображение f(z)=z^4+c, где c комплексная постоянная. Последовательность z(n) определим соотношением z(n+1)=f(z(n)) и начальным условием...
C++ Повторяющиеся элементы массива Есть произвольный массив, в котором нужно отсортировать повторяющиеся элементы по уменьшению и вывести общее кол-во повторений. Решил реализовать следующим образом: сначала просто отсортировать массив методом пузырька, после чего циклом прогнать условие на совпадения, и если они есть просто выводить их на экран и добавлять к счетчику совпадений +1, таким образом избегая пересоздания массива.... http://www.cyberforum.ru/cpp-beginners/thread567034.html
C++ Классы, конструктор копирования (разбор куска программы)
class string{ char *str; void load(char *s) { str=strdup(s); } void add(char *s) { str=(char*)realloc(str,strlen(str)+strlen(s)+1); strcat(str,s); } int find(char *s) { char *p=strstr(str,s); return p==NULL ? -1 : p-str; } int cmp(string &t) { return strcmp(str,t.str); } public: string(){ load(""); } string(char *s){ load(s); }
C++ теоритический вопрос - память
как вычислить адрес(реальный , а не тот который нам ядро подсовывает) какого либо объекта в виртуальной памяти? Добавлено через 5 минут имеется в виду 32 битная адресация
C++ Решение половинным делением. http://www.cyberforum.ru/cpp-beginners/thread567012.html
Составить функцию нахождения корня F(x) = 0 методом деления напополам. Интервал разбить на отрезки с шагом h. Уравнение x*x*x -2 = 0; , h = 0.5. #include <cmath> #include <iostream> #define pi 3.14 using namespace std; double f(double x) {
C++ Перегрузка операции + Всем привет! Ребята, обясните, пжлста, почему конструктор вызывается дважды. Rational integer1( c, d ),h;// инициализация h ( здесь я понимаю почему вызывается конструктор) h=integer + integer1;// а почему вызывается здесь не пойму, ведь должен вызываться operator = Заранее спасибо. подробнее

Показать сообщение отдельно
free334
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
07.05.2012, 20:44  [ТС]     Непростая задача на графы.
Выкладываю весь код. Не судите строго, программист я начинающий)
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
//#include "stdafx.h"
#include <iostream>
#include<vector>
#include<fstream>
using namespace std;
const int MAXN=20000; //максимальное количество вершин
vector<int> g[MAXN],g1[MAXN];  // графы         
bool used[MAXN];
int timer, tin[MAXN], fup[MAXN],points[MAXN];
vector<int> comp;  // компоненты связности
int results[MAXN]; 
int calc(int mas[MAXN]){  //вычисление количества пар вершин
    int result=0,i=0;
    while((i<MAXN)&&(mas[i]!=-1)){
        j=i;
        while((j<MAXN)&&(mas[j]!=-1)){
            result=mas[j]*mas[i]+result;
            j++;
        }
        i++;
    }
    return result;
}
void null(bool mas[MAXN]){ 
    for(int i=0;i<MAXN;i++)
        mas[i]=false;
}
void null(int m[MAXN]){
    for(int i=0;i<MAXN;i++)
        m[i]=-1;
}
void dfs1 (int v) {  //поиск в глубину для нахождения компонентов связности
    used[v] = true;
    comp.push_back (v);
    for (size_t i=0; i<g1[v].size(); ++i) {
        int to = g1[v][i];
        if (! used[to])
            dfs1 (to);
    }
}
 
int find_comps(int n) {  //нахождение размеров компонентов связностей
    int p=0; int sizes[MAXN];
    null(sizes);
    null(used);
    for (int i=0; i<n; ++i)
        if (! used[i]) {
            comp.clear();
            dfs1 (i);
            sizes[p]=comp.size();
            p++;
 
        }
        return calc(sizes);
}
void delete_v(int v,int n){  //удаление всех ребер из данной вершины
    for(size_t i=0;i<n;i++){
        for(size_t j=0;j<g[i].size();j++){
            if(i==v) g1[i].push_back(-1); else
 
                g1[i].push_back(g[i][j]);
 
 
        }
    }
}
 
 
void init(int m[MAXN],int n){  //здесь есть сомнения, какое значение присваивать элементам массива по умолчанию
    for(int i=0;i<n;i++)
        m[i]=n-1;
}
void dfs (int v, int p = -1) {  //нахождение точек сочленения
    used[v] = true; int k=0;
    tin[v] = fup[v] = timer++;
    int children = 0;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (to == p)  continue;
        if (used[to])
            fup[v] = min (fup[v], tin[to]);
        else {
            dfs (to, v);
            fup[v] = min (fup[v], fup[to]);
            if (fup[to] >= tin[v] && p != -1){
                points[k]=v;
                k++;
            }
            ++children;
        }
    }
    if (p == -1 && children > 1){
        points[k]=v;
        k++;
    }
}
void read(int& n){   //считывание
    ifstream in("INPUT.TXT");
    int m,a,b;
    in>>n>>m;
    for(int i=0;i<m;i++){
        in>>a>>b;
        g[a-1].push_back(b-1);
        g[b-1].push_back(a-1);
    }
 
}
int main() {
    int n; int i; vector<int> g1[MAXN];
    ofstream out("OUTPUT.TXT"); 
    null(points);
    read(n);
    init(results,n);
    timer = 0;
    for (i=0; i<n; ++i)
        used[i] = false;
    dfs (0);
    i=0;
    while((i<MAXN)&&(points[i]!=-1)){
        delete_v(points[i],n);
        results[points[i]]=find_comps(n)-n+1;  //огромный-преогромный "костыль", компенсирующий лишнюю компоненту связности  
        i++;
    }
    i=0;
    while(i<n){
 
        out<<results[i]<<endl;
        i++;
    }
 
    return 0;
}
 
Текущее время: 08:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru