С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Моделирование фрактала в координатной плоскости http://www.cyberforum.ru/cpp-beginners/thread567037.html
Требуется написать программу, которая будет строить множество Мандельброта на координатной плоскости и выполнять некоторые функции. Цитирую текст задания:...
C++ Повторяющиеся элементы массива Есть произвольный массив, в котором нужно отсортировать повторяющиеся элементы по уменьшению и вывести общее кол-во повторений. Решил реализовать следующим образом: сначала просто отсортировать... 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); } ...
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...
C++ Перегрузка операции + Всем привет! Ребята, обясните, пжлста, почему конструктор вызывается дважды. Rational integer1( c, d ),h;// инициализация h ( здесь я понимаю почему вызывается конструктор) h=integer +... подробнее

Показать сообщение отдельно
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;
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.