【ABC285_D】 UnionFindで解いてみた 【C++】

abc285のD問題をUnionFindを使って解いてみました。
言語はC++です。

• DFSを使って解いてみた
• BFS(幅優先探索)を使った解き方はこちら

Point

1. a → b → c → aと一巡したらダメそう
   • グラフ理論でいうところのサイクル(閉路)があるかどうかを検出
2. 頂点が文字で与えられている
   • unordered_mapを使って番号に変換
3. UnionFind(dsu)で頂点をグループ化
   • 既に閉路がある場合にさらにつなげる -> No
4. 解けました！

コード例

d.cpp

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, a, b) for (int i = a; i < b; i++)

int main(){
    int n;
    cin >> n;
    //mapだと遅いので基本unordered_mapを使う
    unordered_map<string, int> mp;
    vector<string> s(n), t(n);
    //頂点が文字列 -> mapで頂点数を取得する
    rep(i,0,n){
        cin >> s[i] >> t[i];
        //文字の頂点番号を取得
        //文字が重複したら、最初に記録した頂点番号を採用
        if(!mp.count(s[i])) mp[s[i]]=mp.size();
        if(!mp.count(t[i])) mp[t[i]]=mp.size();
    }
    int m = mp.size(); //頂点数の取得
    //Disjoint Set Union = Union Find (素集合データ構造)
    //素集合...二つの集合が交わりを持たないor互いに素
    //∴共通の元を持たない
    dsu d(m);
    rep(i,0,n){
        //頂点番号の取得
        int u = mp[s[i]];
        int v = mp[t[i]];
        //すでにサイクルが形成されていればアウト
        if (d.same(u, v)){
            cout << "No" << endl;
            return 0;
        }
        //基本的に頂点をつなげるスタイル
        d.merge(u, v);
    }
    cout << "Yes" << endl;
    return 0;
}

解けました！