Advertisement
Guest User

Untitled

a guest
Dec 14th, 2017
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.34 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4.  
  5. std::ifstream file("text.txt");
  6. void DFS(int st,int**graph,bool*visited,int point)
  7. {
  8. int r;
  9. //std::cout<<st+1<<" ";
  10. visited[st]=true;
  11. for (r=0; r < point; r++)
  12.     if ((graph[st][r]!=0) && (!visited[r]))
  13. DFS(r,graph,visited,point);
  14. }
  15.  
  16. bool isConnected(int **graph,bool*visited,int point)
  17. {
  18.     for (int i =0; i < point; i++)
  19.     {
  20.         visited[i]=false;
  21.        
  22.     }  
  23.     DFS(0, graph,visited,point);
  24.     for (int i =0; i < point; i++)
  25.     {
  26.         if (!visited[i])
  27.             return false;
  28.     }
  29.     return true;
  30. }
  31.  
  32. bool prov_del(int **mas_smez,int **maas_isx,int point,bool*visited,int del_reb)
  33. {   if(!isConnected(mas_smez,visited,point))
  34.         return !isConnected(mas_smez,visited,point);
  35.     bool a;
  36.     int**mas_smez1;
  37.     mas_smez1=new int*[point] ;
  38.     for (int i = 0; i < point; ++i)
  39.     {
  40.         mas_smez1[i]=new int[point];
  41.     }
  42.     for (int i = 0; i < point; ++i)
  43.     {
  44.         for (int j = 0; j < point; ++j)
  45.         {
  46.             mas_smez1[i][j]=mas_smez[i][j];
  47.         }
  48.     }
  49.     if(del_reb>1)
  50.     {
  51.         for (int i = 0; i < point ; ++i)
  52.         {
  53.             for (int j = 0; j < point; ++j)
  54.             {
  55.                 if(mas_smez1[i][j]==1)
  56.                 {
  57.                     mas_smez1[i][j]=0;
  58.                     mas_smez1[j][i]=0;
  59.                     maas_isx[i][j]=0;
  60.                     maas_isx[j][i]=0;
  61.                     if(prov_del(mas_smez1,maas_isx,point,visited,del_reb))
  62.                     {  
  63.                         a=prov_del(mas_smez1,maas_isx,point,visited,del_reb);
  64.                         for (int i = 0; i < point; ++i)
  65.                         {
  66.                             delete []mas_smez1[i];
  67.                         }
  68.                         delete []mas_smez1;
  69.                         return a;
  70.                     }
  71.                     maas_isx[i][j]=1;
  72.                     maas_isx[j][i]=1;
  73.                     mas_smez1[i][j]=1;
  74.                     mas_smez1[j][i]=1;
  75.                 }
  76.             }
  77.         }
  78.     }
  79.     else
  80.     {
  81.         for (int i = 0; i < point ; ++i)
  82.         {
  83.             for (int j = 0; j < point; ++j)
  84.             {
  85.                 if(mas_smez1[i][j]==1)
  86.                 {
  87.                     mas_smez1[i][j]=0;
  88.                     mas_smez1[j][i]=0;
  89.                     maas_isx[i][j]=0;
  90.                     maas_isx[j][i]=0;
  91.                     if(!isConnected(mas_smez1,visited,point))
  92.                     {  
  93.                         a = !isConnected(mas_smez1,visited,point);
  94.                         for (int i = 0; i < point; ++i)
  95.                         {
  96.                             delete []mas_smez1[i];
  97.                         }
  98.                         delete []mas_smez1;
  99.                         return a;
  100.                     }
  101.                     maas_isx[i][j]=1;
  102.                     maas_isx[j][i]=1;
  103.                     mas_smez1[i][j]=1;
  104.                     mas_smez1[j][i]=1;
  105.                 }
  106.             }
  107.         }
  108.         return false;  
  109.     }  
  110. }
  111. int main(int argc, char const *argv[])
  112. {
  113.     int **mas_smez;
  114.     int **maas_isx;
  115.     int point;
  116.     bool *visited;
  117.     int a=-1;
  118.     file>>point;
  119.     visited=new bool[point] ;
  120.     mas_smez=new int*[point] ;
  121.     for (int i = 0; i < point; ++i)
  122.     {
  123.         mas_smez[i]=new int[point];
  124.     }
  125.     maas_isx=new int*[point] ;
  126.     for (int i = 0; i < point; ++i)
  127.     {
  128.         maas_isx[i]=new int[point];
  129.     }
  130.     for (int i = 0; i < point; ++i)
  131.     {
  132.         for (int j = 0; j < point; ++j)
  133.         {
  134.             file>>mas_smez[i][j];
  135.         }
  136.     }
  137.     for (int i = 0; i < point; ++i)
  138.     {
  139.         for (int j = 0; j < point; ++j)
  140.         {   maas_isx[i][j]=mas_smez[i][j];
  141.             std::cout<<mas_smez[i][j]<<" ";
  142.         }
  143.         std::cout<<std::endl;
  144.     }
  145.     for (int i = 1; i < point; ++i)
  146.     {
  147.         if(prov_del(mas_smez,maas_isx,point,visited,i))
  148.         {
  149.             a=i;
  150.             break;
  151.         }  
  152.     }
  153.  
  154.     std::cout<<a<<std::endl;
  155.     for (int i = 0; i < point; ++i)
  156.     {
  157.         for (int j = 0; j < point; ++j)
  158.         {  
  159.             std::cout<<maas_isx[i][j]<<" ";
  160.         }
  161.         std::cout<<std::endl;
  162.     }
  163.     for (int i = 0; i < point; ++i)
  164.     {
  165.         delete []mas_smez[i];
  166.     }
  167.     delete []mas_smez;
  168.     for (int i = 0; i < point; ++i)
  169.     {
  170.         delete []maas_isx[i];
  171.     }
  172.     delete []maas_isx;
  173.     delete []visited;
  174.     file.close();
  175.     return 0;
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement