leetcode

0 class UnionFind {

1 int n, cnt = n;

2 vector<int> root, size;

3

4 public:

5 UnionFind(int n) : n(n), root(n), size(n, 1) { iota(root.begin(), root.end(), 0); }

6

7 int find(int x) {

8 while (x != root[x])

9 x = root[x] = root[root[x]];

10 return x;

11 }

12

13 void join(int x, int y) {

14 x = find(x), y = find(y);

15 if (x != y) {

16 if (size[x] > size[y]) swap(x, y);

17 root[x] = y;

18 size[y] += size[x];

19 cnt--;

20 }

21 }

22

23 int count() { return cnt; }

24 bool connected(int x, int y) { return find(x) == find(y); }

25 };

26

27 class Solution {

28 bool similar(const string &s1, const string &s2) {

29 int diff = 0;

30 for (int i = 0; i < s1.size(); i++) {

31 if (s1[i] == s2[i]) continue;

32 if (diff < 2)

33 diff++;

34 else

35 return false;

36 }

37 return true;

38 }

39

40 public:

41 int numSimilarGroups(const vector<string> &strs) {

42 int n = strs.size();

43 UnionFind uf(n);

44 for (int i = 0; i < n; i++) {

45 for (int j = i + 1; j < n; j++) {

46 if (similar(strs[i], strs[j])) uf.join(i, j);

47 }

48 }

49 return uf.count();

50 }

51 };