前言
最____的一集
题目是从正睿OI捞过来的 找不到原题
T1 文件改名
\(n\leq 10^5\)
题意简要：有一堆文件要改名 保证初始的和改正后的名字都没重复
且更改过程中不予许出现重复 求最小操作步数
思考：这题推一下就行
若是状态转移 把这个东西丢到图上
发现可以直接跳过 \(s_i = t_i\) 的情况
然后考虑其它情况
如果是一个图 然后每个点只有一条出边 所以这要么是个链套么是个环 是环答案贡献加一即可
考虑并查集维护
时间复杂度 \(O(n\log n)\)
Code
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,cnt,ans;
int fa[N];
string s1,s2;
map <string,int> mp;
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merges(int u,int v)
{
u=find(u),v=find(v);
if(u==v)
{
ans++;
return;
}
fa[u]=v;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=2*n;i++)
fa[i]=i;
for(int i=1;i<=n;i++)
{
cin>>s1>>s2;
if(s1==s2) continue;
ans++;
if(mp[s1]==0) mp[s1]=++cnt;
if(mp[s2]==0) mp[s2]=++cnt;
merges(mp[s1],mp[s2]);
}
cout<<ans;
return 0;
}