Проверка удаляемости одной вершины орграфа с циклами так, чтобы в полученном орграфе не было циклов, страница 2

  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 clearmem(){  //очистка памяти

  free(ob);

  free(mark);

  destroy_stack(&cicles);

  destroy_stack(&st);

}

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

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

  mark[i]=0;

}

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

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

              if(mark[i]==0) return i;

  return -1;

}

void is_able(int numb,int numbto){   //проверка достижимости numbto из numb. Используется при проверке достижимости вершин, которые были в цикле самих из себя

  if(numb==numbto&&f==0) f=1;   //если не первый раз столкнулись, то все

  if(mark[numb]==0&&f!=1){   //если еще не проходили, текущую вершину и еще не нашли нужную вершину

              if(numbto==numb) f=0;   //инициализация переменной поиска. Первый раз при первом вызове

              mark[numb]=1;   //пометим текущую вершину как пройденную

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

              is_able(ob[numb].nears[i],numbto);   //дальше выполняем обход, если еще не нашли нужную вершину

  }

}

void goth(int numb){   //классический обход в глубину

  if(mark[numb]==0){

              in_stack(&st,numb);   //сохраняем путь в стек

              mark[numb]=1;

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

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

  }

  else{

  int i;    //если встретились с уже пройденной вершиной, то пишем содержимое стека в хранилище.

  for(i=0;i<st.head;i++)

              if(!is_instack(cicles,st.data[i])) in_stack(&cicles,st.data[i]);   //только если их там еще нет

  }

}

int find_vercicles(){     //построение списка вершин, которые состоят в цикле

  int from;

  while((from=find_vertex())!=-1){    //ищем откуда

  goth(from);

  st.head=0;

  };

  if(is_empty(cicles)) return 0;     //если не нашли, то 0

  return 1;//иначе 1

}

void check_vers(){    //проверяем, что будет после удаления вершин

  int i,j;

  int but,nowver;          

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

  for(i=0;i<cicles.head;i++)

  {         

              nowver=cicles.data[i];    //берем вершину из стека

              but=1;

              for(j=0;j<cicles.head&&but;j++)    //и смотрим, будут ли остальные образовывать цикл

                          if(i!=j){

                                      f=2;

                                      clear();

                                      mark[nowver]=2;

                                      is_able(cicles.data[j],cicles.data[j]);

                                      if(f==1) but=0;}

              if(but){       //если нет, то пишем в результат

              result[numbs_res]=nowver;

              numbs_res++;

              } 

  }

}

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

  if(numbs_res==0) printf("No such vertexes.\n");

  else{

  int i;

  printf("Such vertexes are\n");

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

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

  }

}

int main(){

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

  clear();//очистка

  create_stack(&cicles,n);     //создадим хранилища

  create_stack(&st,n);

  if(!find_vercicles()) {printf("No cicles. Check input data.\n");return 0;}   //строим список вершин

  check_vers();     //проверяем, какие из них удовлетворяют условию

  output();   //выводим

clearmem();   //очищаем память

getch();

return 1;

}

7)Тесты

№	Входные данные	Рисунок графа	Результат	Примечание
1	3 0 2 1 2 1 2 0 2 2 2 0 1		No such vertexes.	В любом случае остаются циклы
2	3 0 1 1 1 1 2 2 1 0		Such vertexes are 0 1 2	Простой цикл. При удалении однлй из вершин орграф становится ациклическим.
3	4 0 1 1 1 2 2 3 2 1 0 3 1 0		Such vertexes are 0 1	Два цикла с общими вершинами, которые на стыке удовлетворяют условию
4	6 0 1 1 1 1 2 2 1 0 3 1 4 4 1 5 5 1 3		No such vertexes.	Циклы в разных компонентах сваязности
5	4 0 1 1 1 1 2 2 1 0 3 1 0		Such vertexes are 0 1 2	Одна из вершин не влияет на циклы в орграфе
6	1 0		Atomic graph	Атомарный граф

8)Результаты работы программы

Программа полностью удовлетворяет предъявленным ей требованиям. На всех тестах программа показывает правильный результат.