[Google Question] Determine if given two sentences are similar or not

Problem: This problem is almost same as this problem with an exception that similarity is transitive here. That means if word1 is similar to word2, word2 is similar to word3 then word1 and word3 are also similar.

Example:

Input: sentence1 = ["good","bad","actions"], sentence2 = ["fine","worst","actions"], similarPairs = [["good","fine"],["bad","worst"]]
Output: true
Explanation: The two sentences have the same length and each word wi of sentence1 is also similar to the corresponding word in sentence2.

Approach: We can use Union-Find algorithm here to allow transitivity. Basically we preprocess the similarPairs and build the disjoint sets using Union to take care of the transitivity. Basically it will connect all the words which are similar. 

Once we are done with the above step, we can then check for each word1 in sentence1 to its corresponding word2 in sentence2 if they are equal or are similar using Find. If they are not similar then we can return false. Otherwise we can say that sentence1 and sentence2 are similar.

Implementation in C#:

    public bool AreSentencesSimilarTwo(string[] sentence1, string[] sentence2, IList<IList<string>> similarPairs) 

    {

        if (sentence1.Length != sentence2.Length)

        {

            return false;

        }

        Dictionary<string, int> dsuIndex = new Dictionary<string, int>();

        int count = 0;

        DSUWeighted dsu = new DSUWeighted(similarPairs.Count * 2);

        for (int i = 0; i < similarPairs.Count; ++i)

        {

            if (!dsuIndex.ContainsKey(similarPairs[i][0]))

            {

                dsuIndex.Add(similarPairs[i][0], count++);

            }

            if (!dsuIndex.ContainsKey(similarPairs[i][1]))

            {

                dsuIndex.Add(similarPairs[i][1], count++);

            }

            dsu.Union(dsuIndex[similarPairs[i][0]], dsuIndex[similarPairs[i][1]]);

        }

        for (int i = 0; i < sentence1.Length; ++i)

        {

            if (sentence1[i] == sentence2[i])

            {

                continue;

            }

            if (!dsuIndex.ContainsKey(sentence1[i]) || !dsuIndex.ContainsKey(sentence2[i]) || !dsu.Find(dsuIndex[sentence1[i]], dsuIndex[sentence2[i]]))

            {

                return false;

            }

        }

        return true;

    }

Complexity: O(n * log(p)) where n is the length of sentence and p is the number of pairs.