Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAX = 2e5 + 100;
- const int maxn = 50;
- int n, ans;
- bool allOut;
- string s, t;
- int degin[maxn], degout[maxn];
- int G[maxn][maxn];
- int fa[maxn], cnt[maxn];
- bool vis[maxn];
- void init() {
- for (int i = 0; i < 26; ++i) {
- fa[i] = i;
- cnt[i] = 1;
- }
- }
- int findF(int x) {
- return x == fa[x] ? x : fa[x] = findF(fa[x]);
- }
- void union_(int x, int y) {
- x = findF(x);
- y = findF(y);
- if (x != y) {
- fa[x] = y;
- degout[y] += degout[x];
- cnt[y] += cnt[x];
- }
- }
- int id(char ch) {
- return ch - 'a';
- }
- int main() {
- #ifdef ExRoc
- freopen("test.txt", "r", stdin);
- #endif // ExRoc
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n >> s >> t;
- for (int i = 0; i < n; ++i) {
- G[id(s[i])][id(t[i])] = 1;
- vis[id(s[i])] = true;
- vis[id(t[i])] = true;
- }
- bool allVis = true;
- for (int i = 0; i < 26; ++i) {
- if (!vis[i]) {
- allVis = false;
- }
- for (int j = 0; j < 26; ++j) {
- if (G[i][j] == 1) {
- ++degout[i];
- if (degout[i] > 1) {
- cout << -1 << endl;
- return 0;
- }
- }
- }
- }
- for (int i = 0; i < 26; ++i) {
- if (G[i][i] == 1) {
- --degout[i];
- }
- }
- init();
- for (int i = 0; i < 26; ++i) {
- for (int j = 0; j < 26; ++j) {
- if (G[i][j] == 1) {
- union_(i, j);
- }
- }
- }
- int circle = 0;
- memset(vis, 0, sizeof(vis));
- for (int i = 0; i < 26; ++i) {
- int f = findF(i);
- if (!vis[f]) {
- vis[f] = true;
- if (cnt[f] == degout[f]) {
- ans += degout[f] + 1;
- ++circle;
- } else {
- ans += degout[f];
- }
- }
- }
- if (circle > 0 && allVis) {
- cout << -1 << endl;
- return 0;
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment