Количество компонент связности в дополнении заданного графа

       int gr[NMAX][NMAX];                 /* граф                                           */

       int mtrsv[NMAX][NMAX];         /* матрица связности графа     */

       int kol;                                     /*Количество компонент связности */

printf ("\nZadanie: Podchitat kol-vo         /* Вывод сообщения №1              */

    komponent sviaznosti v dopolnenii zadannogo grafa.\n");

printf ("\n Vvedite kol-vo verchinot 2 do 150\n");  /*Вывод сообщения №2*/

          do

               {   scanf("%d",&n);             /*Ввод количества вершин           */

           if (n<2)

                                             /*Вывод сообщения №7  */

                             printf("\n Error!!!Vvedite kol-vo verchin ot 2 do 150!\n");

          if (n>NMAX)

     /*Вывод сообщения №7           */

                            printf ("\n Error!!!Vvedite kol-vo verchin ot 2 do 150!\n");

               }

            while (n<2||n>NMAX);

      /*Вывод сообщения  №3            */

  printf ("\n Vvedite rebra grafa (ctrl+z).\n");

       vvod (n,gr); /* Матрица смежности              */

  printf("\n Matrica smegnosti:\n\n");      /*Вывод сообщения №4            */

       vivod (n,gr);                                    /*Вывод матрицы смежности    */

       matrica_dopolnenii(n,gr);             /*Матрица дополнения                 */

                                                                /*Вывод сообщения №5               */

 printf ("\n Matrica dopolnenia grafa:\n\n");

       vivod (n,gr);                                    /*Вывод матрицы дополнения     */

       matrica_sviaznosti(n,gr,mtrsv);     /*Матрица связности                  */

   kol=comp_sv(n, mtrsv);           /*Количество компонент связности*/                                                                                                             /* Вывод сообщения №5 и  количество компонент связности     */

    printf("\n\n\n Kolichestvo component sviaznosti:%d",kol);

       getch ();}

    Приложение 3. Текст программы  модуля vvod

     

   /***********************************************************/

   /*    Ввод перечня ребер в матрицу смежности графа gr[] [NMAX] */

   /*                                    Группа 28203  С.Н. Трофимова                         */

   /***********************************************************/ 

    #include"bibl.h"

    vvod (int n,int gr[NMAX][NMAX])

    { int i,j;                                           /* номера вершин                            */

                                                          /* Обнуление графа                         */

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

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

                    gr[i][j]=0;

                                                                /* Ввод ребер графа                         */

    while (scanf("%d%d",&i,&j)==2)

           {

               if (i==j)                              /*Проверка на ошибку ввода         */

                                                          /* Вывод сообщения №8                  */

                      printf ("\n Error!!! Vvedeno nedopustimoe znachenie!\n");

      if (i>=n||i<0||j>=n||j<0)                 /*Проверка на ошибку ввода         */

                                                          /* Вывод сообщения №8                  */

                      printf ("\n Error!!! Vvedeno nedopustimoe znachenie !\n");

           if (gr[i][j]==1)                               /*Проверка на дублирование ребер*/

                                                          /* Вывод сообщения №9                  */

                      printf ("\n Error! Dublirovanie reber!\n");

                      else

                                                         /* Матрица смежности                   */

                       {

                       gr[i][j]=1; gr[j][i]=1;

                       }

         }

    } 
 
 
 
 
 
 
 
 
 
 

Приложение 4. Текст программы  модуля vivod 

   /***********************************************************/

   /*    Вывод матрицы смежности/дополнения графа                            */

   /*                                    Группа 28203  С.Н. Трофимова                         */

   /***********************************************************/

#include"bibl.h"

vivod(int n,int gr[][NMAX])

{  int i,j;  /*Номера вершин                     */

       puts ("  ");

       {               for(i=0;i<n;i++)            /*Построение таблицы матрицы */

                 printf(" %d",i);

                 printf("\n |");

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

                    printf("-");

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

                                             /*Вывод матрицы смежности/дополнения  */

                           {   printf("\n%dі",j);

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

                      printf("%d ", gr[i][j]);

                  }

      } putchar('\n');

}

Приложение 5. Текст программы модуля matrica_dopolnenii 

   /***********************************************************/

   /*    Матрица дополнения графа gr[NMAX][NMAX]                            */

   /*                                    Группа 28203  С.Н. Трофимова                         */

   /***********************************************************/

    #include"bibl.h"

    void matrica_dopolnenii(int n,int gr[NMAX][NMAX])

    { int i,j;                                           /*Номера вершин                            */

                                 /*Построение матрицы дополнения графа                 */

                                /*заменой нулей единицами, единиц - нулями               */

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

                        { for(j=0;j<n;j++)

                                if(gr[i][j]==0)

                                                      gr[i][j]=1;

                                     else

                                                      gr[i][j]=0; }

                    /*Обнуление главной диагонали */

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

             {  gr[i][i]=0; }

    }

Приложение 6. Текст программы  модуля matrica_sviaznosti 

   /***********************************************************/

   /*    Получение матрица связности графа gr[NMAX][NMAX]     с     */

   /*                              использованием алгоритма Уоршела                     */

   /*                                    Группа 28203  С.Н. Трофимова                         */

   /***********************************************************/ 

    #include"bibl.h"

    {       int i,j,k;                                 /*Переменные цикла                 */

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

            {   for(j=0;j<n;j++)

              mtrsv[i][j]=gr[i][j];

            }

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

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

                   if (mtrsv[i][k]==1)

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

                               mtrsv[i][j]=mtrsv[i][j]||mtrsv[k][j];

           } 

Приложение 7. Текст программы модуля comp_sv

   /***********************************************************/

   /*    Подсчет количества компонент связности                                    */

   /*                                    Группа 28203  С.Н. Трофимова                         */

   /***********************************************************/

    #include"bibl.h"

    int  comp_sv(int n, int mtrsv[NMAX][NMAX])

        {     int kol;                            /*Количество компонент связности */

               int i,j;                             /*Переменные цикла, номера вершин*/ 

                  int vp[NMAX];              /*Вектор посещения                           */