Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- class Graph
- {
- private:
- bool orient;
- int n, **arr, *R;
- public:
- Graph (int **matrix, int x)
- {
- n = x;
- arr = matrix;
- }
- void true_result(int* antichain, int m);
- void deep(int x, int k);
- void poisk_comp(int* antichain, int m);
- };
- void Graph::deep(int x, int k)
- {
- R[x] = k+1;
- for (int i = 0; i < n; i++)
- if (arr[x][i] != 0 && R[i] == 0)
- deep (i, k);
- }
- void Graph::poisk_comp(int* antichain, int m)
- {
- bool comp = true;
- for (int i = 0; i < m; i++)
- antichain[i] = R[antichain[i]-1];
- for (int i = 0; i < m; i++)
- for (int j = 0; j < m; j++)
- if (antichain[i] == antichain[j] && i != j)
- {
- comp = false;
- break;
- }
- if (comp == false)
- cout << "NO";
- else cout << "YES";
- }
- void Graph::true_result(int* antichain, int m)
- {
- int i, k = 0;
- R = new int[n]{0};
- for (int i = 0; i < n; i++)
- if (!R[i])
- {
- deep(i, k);
- k++;
- }
- if (k != m)
- cout << "NO";
- else
- poisk_comp(antichain, m);
- }
- int main()
- {
- int n, m;
- cin >> n;
- int **arr = new int*[n];
- for ( int i = 0; i < n; i++)
- arr[i] = new int[n];
- for (int i =0; i < n; i++)
- for (int j =0; j < n; j++)
- cin >> arr[i][j];
- cin >> m;
- int *antichain = new int[m];
- for (int i = 0; i < m; i++)
- cin >> antichain[i];
- Graph object(arr, n);
- object.true_result(antichain, m);
- }
Add Comment
Please, Sign In to add comment