#include <stdio.h>
#include <conio.h>
#include <locale.h>
int vertexCount = -1;//количество вершин графа
FILE *f;
bool detected = false;//true, если найдена ошибка
bool all_used (bool *used, int *x)//проверяет все ли использованы, и возвращает номер не использованной вершины
{
for(int i = 0; i < vertexCount; i++)//проход по списку использованных, пока не будет найдена следующая вершина
if(used[i] == false)
{
*x = i + 1;//запись в переменную значения следующей вершины
return false;
}
return true;//если вершина не найдена, возвращает, что весь граф просмотрен
}
bool **create_array_for_special_vertexes()
{
bool **isolated = new bool *[2];//массив проверяющий "особые" вершины
isolated[0] = new bool [vertexCount];//создание этого массива
isolated[1] = new bool [vertexCount];//продолжение создания
for(int i = 0; i < 2; i++)
for(int j = 0; j < vertexCount; j++)
{
isolated[i][j] = false;
}
return isolated;
}
void zero_used(bool *used)//зануление массива использованных вершин
{
for(int i = 0; i < vertexCount; i++)
used[i] = false;
}
bool belong(int *graph, int vertex)//подпрограмма, которая проверяет принадлежность текущего ребра списку (необходима для удаления мульти-ребер)
{
for(int i = 0; i < vertexCount; i++)
if(graph[i] == vertex)
return true;
return false;
}
int *graphInc(int current, int *graph, bool **isolated)//ввод массивов из которых будет собран граф
{
int start = -1, end = -1, i = 0;
graph = new int [vertexCount - 1];//выделение памяти под часть графа
while(fscanf(f, "%d %d", &start, &end)!= EOF)
{
if(start == end)//отсечение петель
continue;
if(start > vertexCount || end > vertexCount || start == 0 || end == 0)//проверка корекстности введеных данных
{
printf("Граф введен не павильно (указаны ребра до не существующих вершин)");
detected = true;//метка, что из подпрограммы был осуществлен досрочный выход
goto exit;//выход
}
if(start == current && !belong(graph, end))//ввод вершин (если мультиграф, и это ребро уже существует, то не вводит его)
{
isolated[0][start - 1] = true;//отметка в "специальном" массиве, что из данной вершины выходят ребра
isolated[1][end - 1] = true;//отметка, что в данную вершину входят ребра
graph[i] = end;//помещение конца ребра в массив
i++;
}
}
graph[i] = 0;//ввод признака конца в ребра
exit://точка выхода из подпрограммы, если найдена ошибка в исходных данных
return graph;
}
bool stok_head(int current, bool **special)//проверяет, является ли заданная вершина головой стока (возвращает true, если это так)
{
return !(special[0][current - 1]) && special[1][current - 1];
}
void deepSearch(int curent, int **graph, bool *used)//поиск в глубину
{
/*curent - текущая вершина из которой ведется поиск*/
int x = -1;//х - следующая вершина из которой ведется поиск
used[curent - 1] = true;//запись текущей вершины в список использованных
for(int k = 0;graph[curent - 1][k]; k++)//цикл, в котором проходятся все доступные вершины из данной
{
x = graph[curent - 1][k];//присвоение х значения возможной вершины
if(!used[x - 1])//если х не пройден
deepSearch(x, graph, used);//осуществить поиск из вершины х
}
}
void tryToDoSmtng(bool *used, bool **special, int **graph)//поиск минимального подмножества
{
int next = 0;
while(!all_used(used, &next))
{
if(!stok_head(next, special))
{
deepSearch(next, graph, used);
printf("%d ", next);
}
else
used[next - 1] = true;
}
}
void clean(bool *used, bool **special, int **graph)//удаление мусора
{
delete used;
delete graph;
delete special;
}
void main()
{
setlocale(LC_CTYPE, "rus");
f = fopen("count.txt", "r");
fscanf(f, "%d", &vertexCount);
fclose(f);
/*Проверка частных случаев на основе кол-ва вершин*/
if (vertexCount < 0)//ошибка: отрицательное количество вершин графа
{
printf("Число вершин графа не может быть отрицательным");
goto exit;
}
if(!vertexCount)//проверка на пустоту
{
printf("Граф пуст!");
goto exit;
}
if(vertexCount == 1)//частный случай графа (1 вершина)
{
printf("1");
goto exit;
}
/*окончание проверки*/
bool *used = new bool[vertexCount];//массив использованных вершин
zero_used(used);//обнуление массива использованных
f = fopen("input.txt" , "r");//файл с графом
int **graph = new int *[vertexCount];//массив сожержащий граф (в виде списка ребер)
bool **special = create_array_for_special_vertexes();//содержит краткую информацию о каждой вершине (наличие входящих и выходящих ребер)
/*ввод графа*/
for(int i = 0; i < vertexCount; i++)
{
graph[i] = graphInc(i+1, graph[i], special);
fseek(f, 0, SEEK_SET);
if(detected)//если выход был осуществлен досрочно, то выход из программы
goto exit;
}
fclose(f);
/*окончание ввода графа*/
tryToDoSmtng(used, special, graph);//выполнение поставленной задачи
exit://точка досрочного выхода их программы, если найдена ошибка или частный случай
/*Удаление мусора, после выполнения поставленной задачи*/
clean(used, special, graph);
_getch();
}
