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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
free334
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
06.05.2012, 15:11     Непростая задача на графы. #1
Здравствуйте! Необходимо решить такую задачу:
Антон работает в межгалактическом туристическом агентстве. Довольно часто ему приходится прокладывать путь с одной планеты на другую с использованием существующих рейсов космических кораблей. К сожалению, количество рейсов невелико, поэтому пассажирам часто приходится пересаживаться на промежуточных планетах.

Антон заметил, что некоторые планеты используются в качестве промежуточных чаще, чем другие. Он решил провести исследование – для каждой планеты A он хотел бы узнать, сколько существует пар различных планет (B,C), таких что любой путь с планеты B на планету C проходит через планету A.

Помогите Антону!
Входные данные

Первая строка входного файла INPUT.TXT содержит два целых числа: N и M – количество планет и количество рейсов космических кораблей, соответственно (2 <= N <= 20 000, 1 <= M <= 200 000). Следующие M строк описывают рейсы космических кораблей. Каждый рейс связывает две планеты, и им можно воспользоваться в любом из двух направлений. С любой планеты можно добраться до любой другой.
Выходные данные

В выходной файл OUTPUT.TXT выведите N целых чисел – для каждой планеты A выведите количество пар различных планет, таких что любой путь с одной планеты на другую проходит через A.


Уже долго мучаюсь с этой задачей. По-моему алгоритм решения таков: находим в данном графе точки сочленения, потом для каждой найденной точки удаляем все ребра исходящие из него, находим количество элементов в каждой получившейся компоненте связности и вычисляем количество пар вершин в этих компонентах. Если вершина не является точкой сочленения, то количество пар вершин равно N-1. Реализация данного алгоритма заваливается на первых тестах из=за неверного ответа. В чем я неправ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.05.2012, 15:11     Непростая задача на графы.
Посмотрите здесь:

Одна непростая зaдaчка C++
C++ Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0
C++ Задача на графы
C++ задача про графы
C++ Непростая задачка по массивам
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.05.2012, 16:28     Непростая задача на графы. #2
Цитата Сообщение от free334 Посмотреть сообщение
Уже долго мучаюсь с этой задачей.
Цитата Сообщение от free334 Посмотреть сообщение
Если вершина не является точкой сочленения, то количество пар вершин равно N-1.
Вы в ответ для таких вершин выводите N-1 ? Тогда это неправильно, для таких вершин ответ 0.

Цитата Сообщение от free334 Посмотреть сообщение
находим в данном графе точки сочленения, потом для каждой найденной точки удаляем все ребра исходящие из него, находим количество элементов в каждой получившейся компоненте связности и вычисляем количество пар вершин в этих компонентах.
Что Вы выводите в ответ в этом случае?
И еще один вопрос: вы удаляете ребра окончательно для каждой точки сочленения (при просмотре других точек, Вы эти ребра уже не учитываете?)
free334
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
06.05.2012, 18:27  [ТС]     Непростая задача на графы. #3
Вы в ответ для таких вершин выводите N-1 ? Тогда это неправильно, для таких вершин ответ 0.
Тогда почему в примере входных-выходных данных входным данным
7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7
соответствует ответ
18
6
6
6
6
6
6
Может быть я что-то неправильно понял?

Что Вы выводите в ответ в этом случае?
Я делаю массив sizes в который заносятся размеры компонентов связности, потом с помощью простых вычислений:
C++
1
2
3
4
5
6
7
8
9
10
11
12
int calc(int mas[MAXN]){
    int result=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;
}
получаю количество пар вершин. Правда надо учитывать, что я удаляю только ребра, не вершину, и может быть как раз из-за этого получается неправильный ответ. То есть будет лишняя компонента связности размером 1.

вы удаляете ребра окончательно для каждой точки сочленения (при просмотре других точек, Вы эти ребра уже не учитываете?)
Я удаляю ребра, делая второй граф, то есть старый остается неизменным.

Кстати, на этом форуме я нашел тему в которой Вы выложили эту задачу. Вы ее все-таки решили?)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.05.2012, 23:54     Непростая задача на графы. #4
Цитата Сообщение от free334 Посмотреть сообщение
Может быть я что-то неправильно понял?
Вы все правильно поняли.

Цитата Сообщение от free334 Посмотреть сообщение
Я делаю массив sizes в который заносятся размеры компонентов связности, потом с помощью простых вычислений:Код C++
C++
1
2
3
4
5
6
7
8
9
10
11
12
int calc(int mas[MAXN]){
 int result=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;
}
получаю количество пар вершин.
правильнее будет вернуть:
C++
1
return result+N-1;
может быть именно в этом у Вас ошибка.
Лучше покажите весь код.
Кстати, насколько я помню, в этой задаче тяжело было уложиться по времени.

Цитата Сообщение от free334 Посмотреть сообщение
Вы ее все-таки решили?)
да.
free334
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
07.05.2012, 20:44  [ТС]     Непростая задача на графы. #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
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;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.05.2012, 05:40     Непростая задача на графы. #6
Потестировал Ваш код:
на тест:
Цитата Сообщение от free334 Посмотреть сообщение
7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7
вот эта функция:
Цитата Сообщение от free334 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
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);
}
при удалении точки 1, выдает что имеется 4 компоненты связности (должно быть 3) и все имеют размер 2

А например при тесте:
4 3
1 2
2 3
3 4
функция:
Цитата Сообщение от free334 Посмотреть сообщение
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
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++;
 }
}
выдает что точек сочленения всего 1 (должно быть 2)
Но даже если исправить ошибки, то по времени у Вас не получится пройти. Я вспомнил эту задачу и посмотрел свой код - у меня всего два прохода в глубину. Уже на втором проходе вывод результата для каждой вершины. Если интересует мой вариант, могу описать алгоритм.
free334
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
08.05.2012, 18:59  [ТС]     Непростая задача на графы. #7
Да, действительно, недочетов много... Спасибо, что указали ошибки.
Уложиться всего в два обхода в глубину? Интересно, даже очень)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.05.2012, 20:56     Непростая задача на графы. #8
Если коротко то так:
заводим 4 массива:
int res[N] - для хранения результатов
int a[N] - метки вершин при достижении их в глубину (которые остаются без изменений)
int b[N] - метки вершин при достижении их в глубину (которые будут меняться)
bool mas_kontr[N] - помечать уже пройденные вершины.
Заводим глобальную переменную int time=0;
Считываем входные данные и делаем первый проход в глубину (с помощью рекурсии). Первая рекурсивная функция выглядит так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void rec(int n)
{
    // помечаем в mas_kontr[] вершину n
    // изначально a[n]=b[n]=time; time++;
    // перебираем все вершины смежные с n
    {
    // если такая вершина X не помечена, то
    {
        rec(X);
        if(b[X]<b[n])
            b[n]=b[X];
    }
    else
    {
        if(a[X]<b[n])
            b[n]=a[X];
    }
    }
}
вызываем так: rec(0);
после первого прохода, снова приводим массив mas_kontr[] к первоначальному виду (он еще будет участвовать во втором проходе в глубину)
и вызываем вторую рек.функцию:
int rec2(int n)
{
// помечаем вершину n в mas_kontr[] как пройденную
int v=1, tmp2=0, tmp1;
// перебираем вершины смежные с n
// очередная смежная вершина X не помечена, как пройденная
{
tmp1=rec2(X);
if(b[X]==b[n])
{
res[n]+=(N-v-tmp1)*tmp1;
v+=tmp1;
}
else
tmp2+=tmp1;
}
res[n]+=N-1;
return v+tmp2;
}
ее вызов rec2(0);
все.
Потом вывод значений из res[].
free334
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
09.05.2012, 14:10  [ТС]     Непростая задача на графы. #9
Хм, интересно. Вот полный листинг программы по вашему алгоритму.

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
#include "stdafx.h"
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
const int N=10;
vector<int> g[N];
int res[N];
int a[N];
int b[N];
bool mas_kontr[N];
int time=0;
void null(bool mas[N]){
    for(size_t i=0;i<N;i++){
        mas[i]=false;
    }
}
void null(int mas[N]){
    for(size_t i=0;i<N;i++){
        mas[i]=0;
    }
}
void rec(int n)
{
    mas_kontr[n]=true;     
    a[n]=time; 
    b[n]=time; 
    time++;
    for(size_t i=0;i<g[n].size();i++){
        int to=g[n][i];
        if(!mas_kontr[to])
        {
            rec(to);
            if(b[to]<b[n])
                b[n]=b[to];
        }
        else
        {
            if(a[to]<b[n])
                b[n]=a[to];
        }
    }
}
 
 
int rec2(int n)
{
    mas_kontr[n]=true;         
    int v=1, tmp2=0, tmp1;
    for(size_t i=0;i<g[n].size();i++){    
        int  to=g[n][i];
        if(!mas_kontr[to])   
        {
            tmp1=rec2(to);
            if(b[to]==b[n])
            {
                res[n]+=(N-v-tmp1)*tmp1;
                v+=tmp1;
            }
            else
                tmp2+=tmp1;
        }
        res[n]+=N-1;
        return v+tmp2;
    }
}
 
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);
    }
}
 
void init(int m[N],int n){  
    for(int i=0;i<n;i++)
        m[i]=-1;
}
int main()
{
    null(mas_kontr);
    null(res);
    size_t i=0;
    int n;
    ofstream out("OUTPUT.TXT");
    read(n);
    rec(0);
    null(mas_kontr);
    rec2(0);
    while((i<n)&&(res[i]!=-1)){
        out<<res[i]<<endl;
        i++;
    }
    return 0;
}
Но на тест, данный в задании выдается ответ:
17
9
0
0
0
0
0
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.05.2012, 17:44     Непростая задача на графы. #10
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
#include "stdafx.h"
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
const int N=20000;
vector<int> g[N];
int res[N];
int a[N];
int b[N];
bool mas_kontr[N];
int time=0, n;
void null(bool mas[N]){
    for(size_t i=0;i<N;i++){
        mas[i]=false;
    }
}
void null(int mas[N]){
    for(size_t i=0;i<N;i++){
        mas[i]=0;
    }
}
void rec(int nn)
{
    mas_kontr[nn]=true;     
    a[nn]=time; 
    b[nn]=time; 
    time++;
    for(size_t i=0;i<g[nn].size();i++){
        int to=g[nn][i];
        if(!mas_kontr[to])
        {
            rec(to);
            if(b[to]<b[nn])
                b[nn]=b[to];
        }
        else
        {
            if(a[to]<b[nn])
                b[nn]=a[to];
        }
    }
}
 
 
int rec2(int nn)
{
    mas_kontr[nn]=true;         
    int v=1, tmp2=0, tmp1;
    for(size_t i=0;i<g[nn].size();i++){    
        int  to=g[nn][i];
        if(!mas_kontr[to])   
        {
            tmp1=rec2(to);
            if(b[to]==a[nn])
            {
                res[nn]+=(n-v-tmp1)*tmp1;
                v+=tmp1;
            }
            else
                tmp2+=tmp1;
        }
        
    }
    res[nn]+=n-1;
    return v+tmp2;
}
 
void read(){   
    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);
    }
}
 
void init(int m[N],int n){  
    for(int i=0;i<n;i++)
        m[i]=-1;
}
int main()
{
    null(mas_kontr);
    null(res);
    size_t i=0;
    ofstream out("OUTPUT.TXT");
    read();
    rec(0);
    null(mas_kontr);
    rec2(0);
    while((i<n)&&(res[i]!=-1)){
        out<<res[i]<<endl;
        i++;
    }
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.05.2012, 19:55     Непростая задача на графы.
Еще ссылки по теме:

C++ Задача на графы. Удалить ребро, соединяющее вершины a и b
C++ Задача про графы
Интересная задача на графы C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
free334
0 / 0 / 0
Регистрация: 29.04.2012
Сообщений: 9
09.05.2012, 19:55  [ТС]     Непростая задача на графы. #11
Да, очень остроумно) Эдакая модифицированная программа по нахождению точек сочленения.
Спасибо Вам большое, valeriikozlov, за то что Вы не жалея времени помогаете людям.
Yandex
Объявления
09.05.2012, 19:55     Непростая задача на графы.
Ответ Создать тему
Опции темы

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