問題概要

英大文字 2 文字からなる $N$ 個の文字列 $S_{1}, S_{2}, \dots, S_{N}$ が与えられる。

次の条件を満たす文字列の集合のサイズの最小値を求めよ。

任意の $i$ に対して、集合に含まれる文字列が存在して、 $S_{i}$ はその文字列の部分文字列である
集合に含まれる文字列の長さ 2 の任意の部分文字列は、 $S_{1}, S_{2}, \dots, S_{N}$ のいずれかに一致する

制約

$1 \le N \le 26^{2}$

考えたこと

最初は、頂点がアルファベット文字を持たせたグラフを考えた。各 $i$ に対して、文字列 $S_{i}$ の 0 文字目から 1 文字目へと有向辺を張る。

こうしてできたグラフ上で、最小本数のウォークによって、すべての辺を被覆する問題と考えられた。まず、比較的明らかな考察として、強連結成分内ではすべての辺を通るウォークを構築できることに注意しよう。よって、強連結成分分解してできる DAG を考えれば良い。

そうすると「DAG の最小パス被覆」という有名問題が思い浮かんだ。しかし、DAG の最小パス被覆は、辺の被覆ではなく、頂点の被覆を考える問題である。似て非なる。

......そこで、もとのグラフにおいて、頂点と辺を入れ替えることを考えてみた (line graph を考えた)。

頂点と辺を入れ替える

次のグラフを考えよう。

頂点：文字列 $S_{1}, \dots, S_{N}$ に対応する $N$ 個の頂点 (最大で 256 個)
辺： $S_{i}$ の末尾と $S_{j}$ の先頭が等しいとき、有向辺 $(i, j)$ を張る

このグラフ上で、最小本数のウォークによって、すべての頂点を被覆する問題を考えれば良い。先ほどと同様に、強連結成分内部では 1 本のウォークですべての頂点を通るようにできるので、強連結成分分解して、DAG に帰着できる。

今度こそ DAG 上の最小パス被覆を求めれば良いように思われるが、最後に少しだけ罠がある。それは、

DAG の最小パス被覆の問題設定では、パス同士が頂点を共有してはならない

という設定があることだ。今回は、サンプル 2 (下図) でもそうなのだが、パス同士が頂点を共有してもよい。

そこで、DAG の推移閉包をとることにする。つまり、DAG 上で頂点 $i$ を始点とし、頂点 $j$ を終点とするパスが存在するとき、辺 $(i, j)$ を張るのだ。

こうしてできる DAG 上で、今度こそ最小パス被覆を求めればよい。

DAG の最小パス被覆

DAG の最小パス被覆は、蟻本にも載ってる。下図のように「二部グラフの最大マッチング問題」に帰着される。

左側の DAG は、

頂点 0 → 頂点 1 → 頂点 7
頂点 4 → 頂点 2 → 頂点 3
頂点 6 → 頂点 5

という 3 本のパスで被覆されている。これは右側の二部グラフでは、8 - 3 = 5 本のマッチング辺に対応している。

よくみると、左側の 3 本のパスの始点をなす頂点 0, 4, 6 は、右側の二部グラフでは右側ノードでマッチングの端点になっていない頂点たちに対応している。

そんなわけで、「DAG の最小パス被覆の本数」は「頂点数 - 二部グラフの最大マッチングの本数」に一致する。

コード

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


// Edge Class
template<class T> struct Edge {
    int from, to;
    T val;
    Edge() : from(-1), to(-1), val(-1) { }
    Edge(int f, int t, T v = -1) : from(f), to(t), val(v) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        return s << E.from << "->" << E.to;
    }
};

// graph class
template<class T> struct Graph {
    vector<vector<Edge<T>>> list;
    vector<vector<Edge<T>>> reversed_list;
    
    Graph(int n = 0) : list(n), reversed_list(n) { }
    void init(int n = 0) {
        list.assign(n, vector<Edge<T>>());
        reversed_list.assign(n, vector<Edge<T>>());
    }
    const vector<Edge<T>> &operator [] (int i) const { return list[i]; }
    const vector<Edge<T>> &get_rev_edges(int i) const { return reversed_list[i]; }
    const size_t size() const { return list.size(); }
        
    void add_edge(int from, int to, T val = -1) {
        list[from].push_back(Edge(from, to, val));
        reversed_list[to].push_back(Edge(to, from, val));
    }
    
    void add_bidirected_edge(int from, int to, T val = -1) {
        list[from].push_back(Edge(from, to, val));
        list[to].push_back(Edge(to, from, val));
        reversed_list[from].push_back(Edge(from, to, val));
        reversed_list[to].push_back(Edge(to, from, val));
    }

    friend ostream &operator << (ostream &s, const Graph &G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << " -> ";
            for (const auto &e : G[i]) s << e.to << " ";
            s << endl;
        }
        return s;
    }
};

// strongly connected components decomposition
template<class T> struct SCC {
    // input
    Graph<T> G;
    
    // results
    vector<vector<int>> scc;
    vector<int> cmp;
    Graph<T> dag;
    
    // intermediate results
    vector<bool> seen;
    vector<int> vs, rvs;
    set<pair<int,int>> new_edges;
    
    // constructor
    SCC() { }
    SCC(const Graph<T> &graph) : G(graph) { }
    void init(const Graph<T> &graph) { G = graph; }

    // dfs / rdfs
    void dfs(int v) {
        seen[v] = true;
        for (const auto &e : G[v]) if (!seen[e.to]) dfs(e.to);
        vs.push_back(v);
    }
    void rdfs(int v, int k) {
        seen[v] = true;
        cmp[v] = k;
        for (const auto &e : G.get_rev_edges(v)) if (!seen[e.to]) rdfs(e.to, k);
        rvs.push_back(v);
    }

    // reconstruct
    void reconstruct() {
        dag.init((int)scc.size());
        new_edges.clear();
        for (int i = 0; i < (int)G.size(); ++i) {
            int u = cmp[i];
            for (const auto &e : G[i]) {
                int v = cmp[e.to];
                if (u == v) continue;
                if (!new_edges.count({u, v})) {
                    dag.add_edge(u, v);
                    new_edges.insert({u, v});
                }
            }
        }
    }

    // main solver
    vector<vector<int>> find_scc(bool to_reconstruct = true) {
        // first dfs
        seen.assign((int)G.size(), false);
        vs.clear();
        for (int v = 0; v < (int)G.size(); ++v) if (!seen[v]) dfs(v);

        // back dfs
        int k = 0;
        scc.clear();
        seen.assign((int)G.size(), false);
        cmp.assign((int)G.size(), -1);
        for (int i = (int)G.size()-1; i >= 0; --i) {
            if (!seen[vs[i]]) {
                rvs.clear();
                rdfs(vs[i], k++);
                scc.push_back(rvs);
            }
        }

        // reconstruct DAG
        if (to_reconstruct) reconstruct();
        return scc;
    }
};

// edge class (for network-flow)
template<class FLOWTYPE> struct FlowEdge {
    // core members
    int rev, from, to;
    FLOWTYPE cap, icap, flow;
    
    // constructor
    FlowEdge(int r, int f, int t, FLOWTYPE c)
    : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {}
    void reset() { cap = icap, flow = 0; }
    
    // debug
    friend ostream& operator << (ostream& s, const FlowEdge& E) {
        return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')';
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct FlowGraph {
    // core members
    vector<vector<FlowEdge<FLOWTYPE>>> list;
    vector<pair<int,int>> pos;  // pos[i] := {vertex, order of list[vertex]} of i-th edge
    
    // constructor
    FlowGraph(int n = 0) : list(n) { }
    void init(int n = 0) {
        list.assign(n, FlowEdge<FLOWTYPE>());
        pos.clear();
    }
    
    // getter
    vector<FlowEdge<FLOWTYPE>> &operator [] (int i) {
        return list[i];
    }
    const vector<FlowEdge<FLOWTYPE>> &operator [] (int i) const {
        return list[i];
    }
    size_t size() const {
        return list.size();
    }
    FlowEdge<FLOWTYPE> &get_rev_edge(const FlowEdge<FLOWTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    FlowEdge<FLOWTYPE> &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const FlowEdge<FLOWTYPE> &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<FlowEdge<FLOWTYPE>> get_edges() const {
        vector<FlowEdge<FLOWTYPE>> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    
    // change edges
    void reset() {
        for (int i = 0; i < (int)list.size(); ++i) {
            for (FlowEdge<FLOWTYPE> &e : list[i]) e.reset();
        }
    }
    void change_edge(FlowEdge<FLOWTYPE> &e, FLOWTYPE new_cap, FLOWTYPE new_flow) {
        FlowEdge<FLOWTYPE> &re = get_rev_edge(e);
        e.cap = new_cap - new_flow, e.icap = new_cap, e.flow = new_flow;
        re.cap = new_flow;
    }
    
    // add_edge
    void add_edge(int from, int to, FLOWTYPE cap) {
        pos.emplace_back(from, (int)list[from].size());
        list[from].push_back(FlowEdge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(FlowEdge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }

    // debug
    friend ostream& operator << (ostream& s, const FlowGraph &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }
};

// Dinic
template<class FLOWTYPE> FLOWTYPE Dinic
 (FlowGraph<FLOWTYPE> &G, int s, int t, FLOWTYPE limit_flow)
{
    FLOWTYPE current_flow = 0;
    vector<int> level((int)G.size(), -1), iter((int)G.size(), 0);
    
    // Dinic BFS
    auto bfs = [&]() -> void {
        level.assign((int)G.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (const FlowEdge<FLOWTYPE> &e : G[v]) {
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        }
    };
    
    // Dinic DFS
    auto dfs = [&](auto self, int v, FLOWTYPE up_flow) {
        if (v == t) return up_flow;
        FLOWTYPE res_flow = 0;
        for (int &i = iter[v]; i < (int)G[v].size(); ++i) {
            FlowEdge<FLOWTYPE> &e = G[v][i], &re = G.get_rev_edge(e);
            if (level[v] >= level[e.to] || e.cap == 0) continue;
            FLOWTYPE flow = self(self, e.to, min(up_flow - res_flow, e.cap));
            if (flow <= 0) continue;
            res_flow += flow;
            e.cap -= flow, e.flow += flow;
            re.cap += flow, re.flow -= flow;
            if (res_flow == up_flow) break;
        }
        return res_flow;
    };
    
    // flow
    while (current_flow < limit_flow) {
        bfs();
        if (level[t] < 0) break;
        iter.assign((int)iter.size(), 0);
        while (current_flow < limit_flow) {
            FLOWTYPE flow = dfs(dfs, s, limit_flow - current_flow);
            if (!flow) break;
            current_flow += flow;
        }
    }
    return current_flow;
};

template<class FLOWTYPE> FLOWTYPE Dinic(FlowGraph<FLOWTYPE> &G, int s, int t) {
    return Dinic(G, s, t, numeric_limits<FLOWTYPE>::max());
}

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];
    sort(S.begin(), S.end());
    
    // 文字列を頂点としたグラフを強連結成分分解する
    Graph<int> G(S.size());
    for (int i = 0; i < S.size(); i++) {
        for (int j = 0; j < S.size(); j++) {
            if (j == i) continue;
            if (S[i][1] == S[j][0]) G.add_edge(i, j);
        }
    }
    SCC<int> scc_solver(G);
    const auto &scc = scc_solver.find_scc(true);
    auto dag = scc_solver.dag;

    // SCC して得られた DAG の推移閉包をとり、最小パス被覆を求める
    int V = dag.size();
    vector cango(V, vector(V, false));
    for (int i = 0; i < V; i++) {
        cango[i][i] = true;
        queue<int> que;
        que.push(i);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (auto e : dag[v]) {
                if (!cango[i][e.to]) {
                    cango[i][e.to] = true;
                    que.push(e.to);
                }
            }
        }
    }
    FlowGraph<int> FG(V * 2 + 2);
    int s = V * 2, t = V * 2 + 1;
    for (int i = 0; i < V; ++i) {
        FG.add_edge(s, i, 1);
        FG.add_edge(i + V, t, 1);
    }
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (j == i) continue;
            if (cango[i][j]) FG.add_edge(i, j + V, 1);
        }
    }
    auto max_flow = Dinic(FG, s, t);
    cout << V - max_flow << endl;
}