#include using namespace std; /* UnionFind:素集合系管理の構造体(union by rank) isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n)) unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n)) */ struct UnionFind { // The range of node number is u 0 v n-1 vector rank, parents; UnionFind() {} UnionFind(int n) { // make n trees. rank.resize(n, 0); parents.resize(n, 0); for (int i = 0; i < n; i++) { makeTree(i); } } void makeTree(int x) { parents[x] = x; // the parent of x is x rank[x] = 0; } bool isSame(int x, int y) { return findRoot(x) == findRoot(y); } void unite(int x, int y) { x = findRoot(x); y = findRoot(y); if (rank[x] > rank[y]) { parents[y] = x; } else { parents[x] = y; if (rank[x] == rank[y]) { rank[y]++; } } } int findRoot(int x) { if (x != parents[x]) parents[x] = findRoot(parents[x]); return parents[x]; } }; // 辺の定義 struct Edge { long long u; long long v; long long cost; }; bool comp_e(const Edge &e1, const Edge &e2) { return e1.cost < e2.cost; } // 辺を直接比較するための関数 /* Kruskal :クラスカル法で minimum spanning tree を求める構造体 入力: 辺のvector, 頂点数V 最小全域木の重みの総和: sum 計算量: O(|E|log|V|) */ struct Kruskal { UnionFind uft; long long sum; // 最小全域木の重みの総和 vector edges; int V; Kruskal(const vector &edges_, int V_) : edges(edges_), V(V_) { init(); } void init() { sort(edges.begin(), edges.end(), comp_e); // 辺の重みでソート uft = UnionFind(V); sum = 0; for (auto e : edges) { if (!uft.isSame(e.u, e.v)) { // 閉路にならなければ加える uft.unite(e.u, e.v); sum += e.cost; } } } }; int main() { int N, L; cin >> N >> L; int E=(N * N) / 2; vector vec(N); for (int i = 0; i < N; i++) { cin >> vec[i]; } vector edges(E); int count = 0; for (int i = 0; i < N-1; i++) { for (int j = i + 1; j < N; j++) { int sum = 0; for (int k = 0; k < L; k++) { if(vec[i][k] != vec[j][k]) { sum++; } } Edge e = {i, j, sum}; edges[count] = e; count++; } } Kruskal krs(edges, N); cout << krs.sum << endl; return 0; }