#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);
}