[ABC285D] Change Usernames 题解

FFTotoro · 2023-01-16 19:07:15 · 题解

前言

看到了考场上好多人都在用拓扑排序等一类较高级的算法，蒟蒻被震撼了。

解法

这篇题解与其他题解的做法不同，不用图论，不用并查集，只需要使用一个简单好想的算法即可。

考虑一些用户什么时候不能更换用户名：显而易见，当且仅当别人的旧用户名与这个用户的新用户名起了冲突，这个人是不能更换的。

首先我们把能更换用户名的人处理出来，此时他们的旧用户名就不会影响其他人了。这个时候，我们再把先前与这些更换完用户名的人的原用户名有冲突的人拿出来，再取处理他们。

不断重复上述过程，直到所有人都处理完。在处理的某一个时刻，如果“待处理列表”空了且没有处理完所有人，那么一定无解。

“待处理列表”可以用 std::set 存储，“找人”则可以用 std::map 实现。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,c=0; cin>>n;
  vector<pair<string,string> > a(n);
  vector<bool> b(n);
  map<string,int> x,y;
  for(int i=0;i<n;i++){
    cin>>a[i].first>>a[i].second;
    x[a[i].first]=y[a[i].second]=i+1; // 建立 map 映射，方便“找人”
  }
  set<int> d;
  for(int i=0;i<n;i++){
    if(!x[a[i].second]){
      if(y[a[i].first])d.emplace(y[a[i].first]-1); // 放进列表
      b[i]=true; x[a[i].first]=0; c++;
    }
  } // 第一轮扫描全部的人
  while(1){
    if(c==n){
      cout<<"Yes\n";
      return 0;
    } // 处理完了
    set<int> q;
    for(int i:d){
      if(!b[i]&&!x[a[i].second]){
        if(y[a[i].first])q.emplace(y[a[i].first]-1); // 放进列表
        x[a[i].first]=0; c++;
      }
    } // 把可以处理的拿出来处理
    if(q.empty()&&c<n){
      cout<<"No\n";
      return 0;
    } // 列表空了且还没处理完
    d=q; // 更新列表
  }
  return 0;
}