SHOW:
|
|
- or go back to the newest paste.
| 1 | - | #include "bits/stdc++.h" |
| 1 | + | #include <iostream> |
| 2 | - | |
| 2 | + | #include <algorithm> |
| 3 | - | using namespace std; |
| 3 | + | #include <vector> |
| 4 | #include <utility> | |
| 5 | ||
| 6 | using namespace std; | |
| 7 | ||
| 8 | void printMatrix(vector<auto> v) {
| |
| 9 | cout << '\n'; | |
| 10 | for (auto i : v) {
| |
| 11 | for (auto j : i) | |
| 12 | cout << j << ' '; | |
| 13 | cout << '\n'; | |
| 14 | } | |
| 15 | } | |
| 16 | ||
| 17 | void printAnswer(int ref, int sym, bool tran) {
| |
| 18 | cout << "Finitary relation is: "; | |
| 19 | if (ref == 1) cout << "Reflexive, "; | |
| 20 | else if (ref == 0) cout << "AntiReflexive, "; | |
| 21 | - | else if (sym == 0 && ref == 0) cout << "Asymmetric, "; |
| 21 | + | |
| 22 | ||
| 23 | if (sym == 1) cout << "Symmetric, "; | |
| 24 | - | |
| 24 | + | |
| 25 | else cout << "Not-Symmetric, "; | |
| 26 | ||
| 27 | tran ? cout << "Transitive.\n" : cout << "Not-Transitive.\n"; | |
| 28 | } | |
| 29 | ||
| 30 | vector<vector<bool>> transparency(vector<auto> v) {
| |
| 31 | for (int i = 0; i < v.size(); i++) {
| |
| 32 | for (int j = i; j < v.size(); j++) | |
| 33 | swap(v[i][j], v[j][i]); | |
| 34 | } | |
| 35 | return v; | |
| 36 | } | |
| 37 | ||
| 38 | int is_reflexsity(vector<auto>& v) {
| |
| 39 | int cnt = 0; | |
| 40 | for (int i = 0; i < v.size(); i++) | |
| 41 | if (v[i][i] == 1) cnt++; | |
| 42 | return cnt == v.size() ? 1 : cnt == 0 ? 0 : -1; // 1 - Рефлексивность, 0 - Антиреф., -1 - Нерефлексивность | |
| 43 | } | |
| 44 | ||
| 45 | int is_symmetry(vector<auto>& v) {
| |
| 46 | vector<vector<bool>> v2 = v; | |
| 47 | v2 = transparency(v2); | |
| 48 | //printMatrix(v2); | |
| 49 | int cnt = 0; | |
| 50 | - | if (i != j && (v[i][j] * v2[i][j])) cnt++; |
| 50 | + | |
| 51 | for (int j = 0; j < v.size(); j++) {
| |
| 52 | if (i != j && (v[i][j] * v2[i][j])) cnt++; | |
| 53 | } | |
| 54 | } | |
| 55 | if (v == v2 && cnt != 0) return 1; // Симметрия | |
| 56 | if (cnt > 0) return -1; // Несимметрия | |
| 57 | return 0; // Антисимметрия | |
| 58 | } | |
| 59 | ||
| 60 | bool is_transit(vector<auto>& v) {
| |
| 61 | bool ans = 1; | |
| 62 | for (int i = 0; i < v.size(); i++) {
| |
| 63 | for (int j = 0; j < v.size(); j++) {
| |
| 64 | for (int u = 0; u < v.size(); u++) {
| |
| 65 | ans = v[i][j] >= min(v[i][u], v[u][j]); | |
| 66 | ||
| 67 | if (!ans) return ans; // Нетранзитивно | |
| 68 | - | |
| 68 | + | |
| 69 | } | |
| 70 | ||
| 71 | } | |
| 72 | return ans; // Транзитивно | |
| 73 | - | int main() {
|
| 73 | + | |
| 74 | ||
| 75 | int main() {
| |
| 76 | int n, dim, reflex, sym, transit; | |
| 77 | cout << "Input dimensions of set and count of pairs the finitary relation:\n"; | |
| 78 | cin >> dim >> n; | |
| 79 | vector <pair<int,int>> vec(n); | |
| 80 | cout << "Input pairs:\n"; | |
| 81 | for (int i = 0; i < n; i++) | |
| 82 | cin >> vec[i].first >> vec[i].second; | |
| 83 | ||
| 84 | vector <vector<bool>> matrix(dim, vector<bool>(dim)); | |
| 85 | for (int i = 0; i < n; i++) {
| |
| 86 | matrix[vec[i].first-1][vec[i].second-1] = 1; | |
| 87 | } | |
| 88 | ||
| 89 | printMatrix(matrix); | |
| 90 | reflex = is_reflexsity(matrix); | |
| 91 | - | |
| 91 | + | |
| 92 | transit = is_transit(matrix); | |
| 93 | ||
| 94 | printAnswer(reflex, sym, transit); | |
| 95 | system("Pause");
| |
| 96 | return 0; | |
| 97 | } |