include stdio struct data struct data next int second include stack До

  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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <stdio.h>
struct data{struct data *next; int second;};
#include "stack.h"
//Добавить новый элемент в список смежности
void add_element(int first, int second, data **graph)
{
data *p;
if(graph[first-1]==NULL)
{
graph[first-1]=new data;
graph[first-1]->second=second;
graph[first-1]->next=NULL;
}
else
{
for(p=graph[first-1];p->next!=NULL;p=p->next);
p->next=new data;
p=p->next;
p->second=second;
p->next=NULL;
}
}
//Создаем список смежности
int create_list(FILE *fp, int n, data **graph)
{
int i,first,second;
if(n>1)
{
for(i=0;fscanf(fp,"%d-%d",&first,&second)!=EOF;i++)
add_element(first,second,graph);
return 1;
}
else return 0;
}
int search(int n, data **graph, int a, int b)
{
list *stack;
data *p;
int amt=0, i, m, r=0,sr=0, *peaks=new int[n];
for(i=0;i<n;i++)
peaks[i]=0;
creatstack(&stack);
for(p=graph[a-1];p->next!=NULL;p=p->next)
intostak(&stack,p->second);
intostak(&stack,p->second);
//Обход графа в глубину
while(nullstak(stack))
{
outstak(&stack,&m);
if(r)
{
for(i=0;i<n&&peaks[i]!=amt-1;i++);
if(i!=n)
if(peaks[i]<m)
for(i=0;i<n;i++)
peaks[i]++;
r=0;
sr=1;
}
if(m!=b)
{
peaks[m-1]++;
for(p=graph[m-1];p->next!=NULL;p=p->next)
intostak(&stack,p->second);
intostak(&stack,p->second);
}
else
{
amt++;
r=1;
}
}
//Ищем нужную вершину из множества всех вершин
if(sr==1) amt++;
for(i=0;i<n&&peaks[i]!=amt;i++);
if(i!=n)
return i+1;
else return -1;
}
int achievable(int n, data **graph, int a, int b)
{
list *stack;
int i,m, *flag=new int[n];
data *p;
for(i=0;i<n;i++)
flag[i]=0;
creatstack(&stack);
for(p=graph[a-1];p->next!=NULL;p=p->next)
intostak(&stack,p->second);
intostak(&stack,p->second);
while(nullstak(stack))
{
outstak(&stack,&m);
if(graph[m-1]!=NULL&&m!=b)
{
flag[m-1]=1;
for(p=graph[m-1];p->next!=NULL;p=p->next)
intostak(&stack,p->second);
intostak(&stack,p->second);
}
}
flag[a-1]=1;
flag[b-1]=1;
flag[n-1]=1;
for(i=0;i<n&&flag[i];i++);
if(i==n)
return 1;
else
return 0;
}
int main()
{
FILE *fp, *fp2=fopen("result.txt","w+");
int n,i,a,b,result;
data *p, **graph;
if(fp=fopen("graph.txt","r"))
{
fscanf(fp,"key: %d\n",&n);
fscanf(fp,"a: %d\n",&a);
fscanf(fp,"b: %d\n",&b);
data **graph=new data *[n];
for(i=0;i<n;i++) graph[i]=NULL;
if(create_list(fp,n,graph)) //Создаем список смежности
{
if(achievable(n,graph,a,b))
{
result=search(n,graph,a,b); //Ищем нужную вешину
if(result==-1)
fprintf(fp2,"Ошибка: Вершина не найдена;");
else
fprintf(fp2,"Вершина найдена: %d;",result);
}
else fprintf(fp2,"Ошибка: Точки Вершина В не достяжима из А (или наоборот);");
}
else fprintf(fp2,"Ошибка: Граф пуст");
fclose(fp);
} else fprintf(fp2,"Ошибка: Не могу прочитать входной файл;");
fclose(fp2);
}