allia

поиск антицепи

Jan 16th, 2021 (edited)
202
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. class Graph
  5. {
  6.   private:
  7.   bool orient;
  8.   int n, **arr, *R;
  9.  
  10.   public:
  11.   Graph (int **matrix, int x)
  12.   {
  13.     n = x;
  14.     arr = matrix;
  15.   }
  16.   void true_result(int* antichain, int m);
  17.   void deep(int x, int k);
  18.   void poisk_comp(int* antichain, int m);
  19. };
  20.  
  21. void Graph::deep(int x, int k)
  22. {
  23.   R[x] = k+1;
  24.   for (int i = 0; i < n; i++)
  25.     if (arr[x][i] != 0 && R[i] == 0)
  26.       deep (i, k);
  27. }
  28.  
  29. void Graph::poisk_comp(int* antichain, int m)
  30. {
  31.   bool comp = true;
  32.  
  33.   for (int i = 0; i < m; i++)
  34.       antichain[i] = R[antichain[i]-1];
  35.  
  36.     for (int i = 0; i < m; i++)
  37.      for (int j = 0; j < m; j++)
  38.       if (antichain[i] == antichain[j] && i != j)
  39.         {
  40.           comp = false;
  41.           break;
  42.         }
  43.        
  44.     if (comp == false)
  45.      cout << "NO";
  46.     else cout << "YES";
  47. }
  48.  
  49. void Graph::true_result(int* antichain, int m)
  50. {
  51.   int i, k = 0;
  52.   R = new int[n]{0};
  53.  
  54.   for (int i = 0; i < n; i++)
  55.     if (!R[i])
  56.       {
  57.         deep(i, k);
  58.         k++;
  59.       }
  60.  
  61.   if (k != m)
  62.     cout << "NO";
  63.   else
  64.     poisk_comp(antichain, m);
  65. }
  66.  
  67. int main()
  68. {
  69.  int n, m;
  70.  cin >> n;
  71.  
  72. int **arr = new int*[n];
  73.  
  74. for ( int i = 0; i < n; i++)
  75.      arr[i] = new int[n];
  76.    
  77. for (int i =0; i < n; i++)
  78.   for (int j =0; j < n; j++)
  79.     cin >> arr[i][j];
  80.  
  81. cin >> m;
  82. int *antichain = new int[m];
  83.  
  84. for (int i = 0; i < m; i++)
  85.  cin >> antichain[i];
  86.  
  87.  Graph object(arr, n);
  88.  object.true_result(antichain, m);
  89. }
Add Comment
Please, Sign In to add comment