20221113_T1A-_并查集

题意

在一个文件目录下有 \(n\) 个不同的文件，每个文件都有一个文件名，其中第 \(i\) 个文
件的文件名为 \(s_i\)。这些文件名两两不同。
小 C 希望更改一部分文件的文件名，他对于每个文件都拟定了它的目标文件名，
其中第 \(i\) 个文件的目标文件名为 \(t_i\)。同样地，所有目标文件名也是两两不同的。
为了更改文件名，小 C 需要进行若干次的重命名操作。每次重命名，小 C 可以选
一个文件，将其文件名改成任意字符串。不过，重命名要求遵循这样的规则：每次重命
名之后，所有这 \(n\) 个文件的文件名仍应两两不同。
那么，小 C 至少要进行多少次重命名操作，才能使所有文件名都改成相应的目标
文件名呢？

题解

赛时得分：100/100

非常显然，如果遇到了环那么答案就 +1，如果这个环是环是自环那么答案 -1，一条链那么对答案没有影响（意思是交换就行了）。

现在就是怎么判环的问题了。并不难，我们直接并查集，如果查到两个东西本来就在一个集合里了，那么说明有环了。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N = 1e5 + 10, inf = 0x3f3f3f3f;

int n, cnt, fa[N], ans;
map<string, int>mp;
string st[N], st1[N];
int findf(int x) {
    if(fa[x] == x) return x;
    else return fa[x] = findf(fa[x]);
}

int main() {
    freopen("files.in", "r", stdin);
    freopen("files.out", "w", stdout);
    read(n);
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 1; i <= n; ++i) {
        cin >> st[i] >> st1[i];
        if(!mp.count(st1[i])) mp[st1[i]] = i;
    }
    for(int i = 1; i <= n; ++i) {
        if(st[i] == st1[i]) {
            --ans;
            continue;
        }
        if(mp.count(st[i])) {
            int k = i, l = mp[st[i]];
            if(findf(k) == findf(l)) {
                // cout << k << ' ' << l << endl;
                ++ans;
            } else fa[findf(l)] = findf(k);
        }
    }
    cout << ans + n << endl;
    return 0;
}