CodeThanksFestival2014 H問題 しりとりゲーム

もとにある文字列でしりとりしていくゲーム。足りない単語数は？というのが問題(適当)

今回、単語の最初と最後を使ってグラフを作るというのはすぐに気づいた。
問題はこれを一筆書きするのだが、オイラー閉路なんてもの知らなかった…これめっちゃ有名なやつじゃん…

グラフを一筆書きできる条件は、グラフの頂点の次数がすべて偶数 or 次数が奇数の頂点が2つだけ。

ということですべての頂点が連結になり、かつオイラー閉路の条件を満たせば良い。
連結ではない頂点群を連結するためには、スライドにあるような処理をすれば良い。
これは結構まとめられて、すごいスッキリしたコードになるので実際の処理は簡単♪
うまくまとめることって大事だ…

struct UnionFind
{
    std::vector<int> data;
    UnionFind(int size) : data(size, -1){}
    void initialize(void){
        for(int i=0; i<(int)data.size(); i++) data[i] = i;
    }
    bool merge(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return false;
        else{ data[x] = y; return true; }
    }
    int find(int x){ //根っこを見つける関数
        if(data[x] == x) return x;
        else return data[x] = find(data[x]); //経路圧縮
    }
    bool isSame(int x, int y){
        return find(x) == find(y);
    }
};

const int AL = 26;
int N;
UnionFind uf(AL);
int edge[AL];
vector<int> G[AL];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    uf.initialize();
    cin >> N;
    rep(i, N){
        string s; cin >> s;
        int f = s.front()-'a';
        int b = s.back()-'a';
        uf.merge(b, f);
        edge[f]++; edge[b]++;
    }

    rep(i, AL) G[uf.find(i)].push_back(edge[i]);

    int res = 0;
    rep(i, AL){
        if(len(G[i]) == 0 || edge[i] == 0) continue;
        int n_odd = 0; //奇点の数
        for(int a : G[i]) if(a&1) n_odd++;
        res += max(n_odd/2-1, 0)+1;
    }


    cout << res-1 << endl;
}