Проверка возможности удаления из заданного графа (не дерево) одной вершины (вместе с инцидентными ей ребрами), чтобы в результате получилось дерево, страница 3

            if(n==0) {printf("Graph is empty!\n");//пустой граф

                          getch();

                          return 0;}

            if(n==1) {printf("Atomic graph.\n");//атомарный граф

                          getch();

                          return 0;}

            ob=(graph_v*)calloc(n,sizeof(graph_v));//память под граф

            mark=(int*)calloc(n,sizeof(int));//память под массив марок

            int j;

            for(i=0;i<n;i++)

            {fscanf(f,"%d",&ob[i].number);

                        fscanf(f,"%d",&ob[i].degree);//номер и степень

                        if(ob[i].degree!=0)

                       {ob[i].nears=(int*)calloc(ob[i].degree,sizeof(int));//создаем список смежности

                         for(j=0;j<ob[i].degree;j++)

                         fscanf(f,"%d",&ob[i].nears[j]);};}

            return 1;}

void clear(){//очистка марок

            for(int i=0;i<n;i++)

            mark[i]=0;}

int goneall(){//поиск не пойденных вершин

            int i;

            for(i=0;i<n;i++)

                        if(mark[i]==0) return 0;//нашли нарушителя - значит да

            return 1;//иначе все нормально}

void goth(int numb){//обход в глубину

            if(mark[numb]==0){

                        mark[numb]=1;

                        for(int i=0;i<ob[numb].degree;i++)

                        goth(ob[numb].nears[i]);}}

void output(){//вывод

            if(numb_res==0) printf("There are no such vertexes.\n");

            else{

            printf("Vertexes:\n");

            for(int i=0;i<numb_res;i++)

                        printf("%d ",result[i]);

            printf("\nare satisfied with task.");}}

int find_vertex(){//находим вершину, с которой можно начинать обход

            for(int i=0;i<n;i++)

                        if(mark[ob[i].number]==0) return ob[i].number;

            return -1;}

int is_svyaz(int numbs){//проверка на связность

            clear();//очищаем массив марок

            mark[numbs]=2;//помечаем удаленную вершину

            goth(find_vertex());//обходим

            if(goneall()) return 1;//если все прошли, то связен

            else return 0;}

int numb_rebs(int numbs){//количество ребер

            int sum=0,numb_reb;//накопим и посчитаем

            for(int i=0;i<n;i++)

                        sum+=ob[i].degree;

            numb_reb=(sum/2)-ob[numbs].degree;

            return numb_reb;}

void in_result(int numb){//добавление вершины в результат

            result[numb_res]=numb;

            numb_res++;}

int main(){if(input()==0) return 0;//ввод

            result=(int*)calloc(n,sizeof(int));//выделяем память

            int i;

            for(i=0;i<n;i++)

                        //если граф связен и количество ребер равно n-1, то граф - дерево

                        if(is_svyaz(ob[i].number)&&numb_rebs(ob[i].number)==n-2) in_result(ob[i].number);

output();

getch();

return 1;}

7. Набортестов.

№ теста	Содержание файла	Графическое представление	Результат	Пояснения
1	3 0  2  1 2 1  2  0 2 2  2  0 1		Vertex: 0 1 2 are satisfied with task	Цикл из трех вершин, удовлетворяет условию
2	8 0  2  1 2 1  2  0 3 2  2  0 4 3  2  1 5 4  2  2 5 5  2  3 4 6  2  7 8 7  1  6 8  1  6		There are no such vertexes	Есть висячие вершины – нарушено условие связности, содержит цикл
3	4 0  1  1 1  1  0 2  1  3 3  1  2		There are no such vertexes	Есть висячие вершины
4	7 0  2  1 2 1  3  0 3 4 2  3  0 5 6 3  2  1 4 4  2  1 3 5  1  2 6  1  2		Vertex: 3 4 are satisfied with task	Граф содержит цикл, при удалении одной из вершины которого получаем дерево
5	4 0  3  1 2 3 1  3  0 2 3 2  3  0 1 3 3  3  0 1 2		There are no such vertexes	Содержит больше одного цикла

8. Результат отладки и анализ программы.

            Программа работает правильно, что подтверждается результатами тестов.