Dmaxiya

xxxxx

Apr 1st, 2025
768
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 2e5 + 100;
  4. const int maxn = 50;
  5. int n, ans;
  6. bool allOut;
  7. string s, t;
  8. int degin[maxn], degout[maxn];
  9. int G[maxn][maxn];
  10. int fa[maxn], cnt[maxn];
  11. bool vis[maxn];
  12.  
  13. void init() {
  14.     for (int i = 0; i < 26; ++i) {
  15.         fa[i] = i;
  16.         cnt[i] = 1;
  17.     }
  18. }
  19.  
  20. int findF(int x) {
  21.     return x == fa[x] ? x : fa[x] = findF(fa[x]);
  22. }
  23.  
  24. void union_(int x, int y) {
  25.     x = findF(x);
  26.     y = findF(y);
  27.     if (x != y) {
  28.         fa[x] = y;
  29.         degout[y] += degout[x];
  30.         cnt[y] += cnt[x];
  31.     }
  32. }
  33.  
  34. int id(char ch) {
  35.     return ch - 'a';
  36. }
  37.  
  38. int main() {
  39. #ifdef ExRoc
  40.     freopen("test.txt", "r", stdin);
  41. #endif // ExRoc
  42.  
  43.     ios::sync_with_stdio(false);
  44.     cin.tie(nullptr);
  45.  
  46.     cin >> n >> s >> t;
  47.     for (int i = 0; i < n; ++i) {
  48.         G[id(s[i])][id(t[i])] = 1;
  49.         vis[id(s[i])] = true;
  50.         vis[id(t[i])] = true;
  51.     }
  52.     bool allVis = true;
  53.     for (int i = 0; i < 26; ++i) {
  54.         if (!vis[i]) {
  55.             allVis = false;
  56.         }
  57.         for (int j = 0; j < 26; ++j) {
  58.             if (G[i][j] == 1) {
  59.                 ++degout[i];
  60.                 if (degout[i] > 1) {
  61.                     cout << -1 << endl;
  62.                     return 0;
  63.                 }
  64.             }
  65.         }
  66.     }
  67.     for (int i = 0; i < 26; ++i) {
  68.         if (G[i][i] == 1) {
  69.             --degout[i];
  70.         }
  71.     }
  72.     init();
  73.     for (int i = 0; i < 26; ++i) {
  74.         for (int j = 0; j < 26; ++j) {
  75.             if (G[i][j] == 1) {
  76.                 union_(i, j);
  77.             }
  78.         }
  79.     }
  80.     int circle = 0;
  81.     memset(vis, 0, sizeof(vis));
  82.     for (int i = 0; i < 26; ++i) {
  83.         int f = findF(i);
  84.         if (!vis[f]) {
  85.             vis[f] = true;
  86.             if (cnt[f] == degout[f]) {
  87.                 ans += degout[f] + 1;
  88.                 ++circle;
  89.             } else {
  90.                 ans += degout[f];
  91.             }
  92.         }
  93.     }
  94.     if (circle > 0 && allVis) {
  95.         cout << -1 << endl;
  96.         return 0;
  97.     }
  98.     cout << ans << endl;
  99.  
  100.     return 0;
  101. }
  102.  
Advertisement
Add Comment
Please, Sign In to add comment