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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ferodot
0 / 0 / 0
Регистрация: 21.04.2014
Сообщений: 5
#1

Вывести станции в порядке их закрытия - C++

24.05.2014, 19:58. Просмотров 319. Ответов 2
Метки нет (Все метки)

В городе есть метро, состоящее из N станций и M линий, соединяющих их. Каждая линия обеспечивает проезд между любыми двумя станциями в обе стороны. Между любой парой станций проведено не более одной линии. С каждой станции можно было проехать на каждую (возможно, через промежуточные станции). Назовем это свойство связностью метро. Работу метро решили прекратить. Решено закрывать каждый год по одной станции, но так, чтобы связность метро сохранялась. При закрытии какой-либо станции линии, ведущие от этой станции к другим тоже перестают функционировать. По введенной информации о сети метро разработать какой-либо порядок закрытия станций, при котором метро всегда будет оставаться связным.
Входные данные. Первая строка входного файла будет содержать числа N и M. В следующих М строках находится информация о линиях. Каждая из этих строк содержит через пробел числа Ai и Bi (Ai, Bi) — две станции, которые соединяет i-я линия.
Выходные данные. Выходной файл должен состоять из N строк. Каждая строка должна содержать одно число — номер станции. Вывести станции нужно в порядке их закрытия.

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
#include <iostream>
using namespace std;
 
const int MaxN = 1000,
          MaxP = 5000;
 
int i,j,N,P;
int pre[MaxN], rank[MaxN], color[MaxN];
int B[MaxP], E[MaxP];
int R[MaxP], kG[MaxN], G[MaxN][MaxN];
FILE* file;
 
void Input()
{
    file = fopen("input.txt","r");
    fscanf(file,"%d %d", &N, &P);
    for(i = 1; i <= P; i++)
    {
        fscanf(file,"%d %d", &B[i], &E[i]);
        R[i] = 1;
    }
    fclose(file);
}
 
void MakeSet(int x)
{
    rank[x] = 0;
    pre[x] = x;
}
 
int FindSet(int x)
{
    int z;
    if(x != pre[x])
        pre[x] = FindSet(pre[x]);
    z = pre[x];
    return z;
}
 
void Link(int x, int y)
{
    if (rank[x] > rank[y])
        pre[y] = x;
    else
    {
        pre[x] = y;
        if (rank[x] == rank[y])
            rank[y]++;
    }
}
 
void Union(int x, int y)
{
    Link(FindSet(x),FindSet(y));
}
 
void MinTreeKruskal()
{
    for(i = 1; i <= N; i++)
        kG[i] = 0;
    for(i = 1; i <= N; i++)
        MakeSet(i);
    for(i = 1; i <= P; i++)
        if(FindSet(B[i]) != FindSet(E[i]))
        {
            kG[B[i]]++; G[B[i]][kG[B[i]]];
            kG[E[i]]++; G[E[i]][kG[E[i]]];
            Union(B[i],E[i]);
        }
}
 
void DFS(int u)
{
int j;
color[u] = 1;
for(j = 1; j <= kG[u]; j++)
    if(color[G[u][j]] == 0)
        DFS(G[u][j]);
cout << u << endl;
}
 
void main()
{
Input();
MinTreeKruskal();
for(i = 1; i <= N; i++)
    color[i] = 0;
DFS(1);
system("pause");
}
Переделывал с Паскаля, и выдает ошибки:
error C2872: 'rank' : ambiguous symbol

Помогите исправить, пожалуйста, а то я в этом не сильно разбираюсь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2014, 19:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вывести станции в порядке их закрытия (C++):

Классы (по введенному названию станции вывести из ф-ции мгц) - C++
Можете помочь, вот я писал программу по классам но у меня возникла проблема, мне нужно в основной программе по введенному названию станции...

Вывести все четные числа массива в порядке возрастания их индексов, а затем все нечетные в порядке убывания - C++
Дан целочисленный массив размера N.Вывести в начале все содержащиеся в данном массиве четные числа в порядке возрастания их индексов, а...

Вывести числа в порядке возрастания, по одному в строке. Если между M и N нет простых - вывести "Absent" - C++
Снова всем здравствуйте! Вот до боли знакомая задача, но на промежутке функция работает не оптимально, хотя сама функция оптимизирована....

Вывести в порядке - C++
Вывести в порядке возрастания все обыкновенные несократимые дроби,заключенные между 0 и 1, знаменатели которых не превышают 15. Массив при...

Вывести в обратном порядке - C++
Прежде чем закидать меня камнями потому что программа написано ужасно через одно место и не совсем универсальна и вообще с кучей...

Вывести слова в алфавитном порядке - C++
С клавиатуры читается последовательность строк. Напечатать ее в лексикографическом порядке.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
nmcf
5310 / 4630 / 1550
Регистрация: 14.04.2014
Сообщений: 18,437
24.05.2014, 22:27 #2
В пространстве std уже есть имя rank, замени на другое.
ferodot
0 / 0 / 0
Регистрация: 21.04.2014
Сообщений: 5
25.05.2014, 12:31  [ТС] #3
Спасибо большое за помощь, помогло. Оказывается все просто.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2014, 12:31
Привет! Вот еще темы с ответами:

Как вывести в порядке возрастания? - C++
#include &lt;iostream&gt; using namespace std; int main(){ int a,b,c; cin&gt;&gt;a&gt;&gt;b&gt;&gt;c; if(a&gt;b&amp;&amp;a&gt;c) cout&lt;&lt;a; if(b&gt;a&amp;&amp;b&gt;c) cout&lt;&lt;b;...

Вывести строку в обратном порядке - C++
нужно вывести строку в обратном порядку .где ошибка? #include &lt; iostream&gt; #include &lt;conio.h&gt; #include&lt;cstring&gt; using namespace...

Вывести массив в обратном порядке - C++
Дано действительные числа а1,...,а17. нужно получить a11,a12,...,a17,a10,a9,...,a1.

Вывести слова в обратном порядке - C++
Всем известно, что у каждого важного общественного деятеля есть собственный спичрайтер – существо, помогающее подготовить публичную речь,...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru