🟫

ABC285-D: Change Usernames 解説

2023/01/16に公開

問題

N人いてi番目の人の名前はS_iです。
i番目の人は名前をT_iに変更したいです。
適切な順序で名前を変更することで2人以上の人が同じ名前となる瞬間が存在しないように全員名前を変更することができるか判定してください。

https://atcoder.jp/contests/abc285/tasks/abc285_d

解説

  • AさんがBという名前にしたい、BさんがCという名前にしたいという情報があった時、AさんはBさんが名前を変更してから出ないと変更できない
  • この情報から名前をラベルとした有向グラフで表現できる
    • 上述の状況はA \rightarrow B \rightarrow Cとなる
  • グラフで表現したときに有向閉路ができるとき、そのサイクルに含まれる人たちは誰も名前を変更することができない
  • サイクルが存在するかを判定すれば良い(サイクル検出はググれば出るのでそれを元に変更する)
    • 今回の制約上UnionFindで判定してもOKらしい
  • 文字列の出現順でラベルを振って、一般的なグラフとして扱うテクニックがある

https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-6-サイクル検出

コード
#include<bits/stdc++.h>
using namespace std;

using Graph = vector<vector<int>>;
vector<int> detectCycle(int n, Graph &g){
  const int UNUSED = 0;
  const int USING = 1;
  const int USED = 2;
  vector<int> status(n, UNUSED);
  vector<int> pre(n);
  vector<int> cycle;

  function<bool(int)> dfs = [&](int u) -> bool{
    status[u] = USING;
    for(auto &v: g[u]){
      if(status[v] == UNUSED){
        pre[v] = u;
        if(dfs(v)) return true;
      }else if(status[v] == USING){
        int cur = u;
        while(cur != v){
          cycle.push_back(pre[cur]);
          cur = pre[cur];
        }
        cycle.push_back(u);
        return true;
      }
    }
    status[u] = USED;
    return false;
  };

  for(int i = 0; i < g.size(); ++i){
    if(status[i] == UNUSED && dfs(i)){
      reverse(cycle.begin(), cycle.end());
      return cycle;
    }
  }
  return {};
};


int main(){
  int N;
  cin >> N;
  unordered_map<string, int> nameToI;
  vector<pair<int,int>> edge;
  for(int i = 0; i < N; ++i){
    string s, t;
    cin >> s >> t;
    int S, T;
    if(nameToI.count(s)) S = nameToI[s];
    else S = nameToI[s] = nameToI.size();

    if(nameToI.count(t)) T = nameToI[t];
    else T = nameToI[t] = nameToI.size();

    edge.push_back({S, T});
  }

  Graph G(nameToI.size());
  for(auto &[u, v]: edge) G[u].push_back(v);

  auto r = detectCycle(nameToI.size(), G);
  if(r.empty()) cout << "Yes" << endl;
  else cout << "No" << endl;
}

https://atcoder.jp/contests/abc285/submissions/38103771

GitHubで編集を提案

Discussion