<p>Two strings, <code>X</code> and <code>Y</code>, are considered similar if either they are identical or we can make them equivalent by swapping at most two letters (in distinct positions) within the string <code>X</code>.</p>

<p>For example, <code>&quot;tars&quot;</code>&nbsp;and <code>&quot;rats&quot;</code>&nbsp;are similar (swapping at positions <code>0</code> and <code>2</code>), and <code>&quot;rats&quot;</code> and <code>&quot;arts&quot;</code> are similar, but <code>&quot;star&quot;</code> is not similar to <code>&quot;tars&quot;</code>, <code>&quot;rats&quot;</code>, or <code>&quot;arts&quot;</code>.</p>

<p>Together, these form two connected groups by similarity: <code>{&quot;tars&quot;, &quot;rats&quot;, &quot;arts&quot;}</code> and <code>{&quot;star&quot;}</code>.&nbsp; Notice that <code>&quot;tars&quot;</code> and <code>&quot;arts&quot;</code> are in the same group even though they are not similar.&nbsp; Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.</p>

<p>We are given a list <code>strs</code> of strings where every string in <code>strs</code> is an anagram of every other string in <code>strs</code>. How many groups are there?</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> strs = [&quot;tars&quot;,&quot;rats&quot;,&quot;arts&quot;,&quot;star&quot;]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> strs = [&quot;omv&quot;,&quot;ovm&quot;]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= strs.length &lt;= 300</code></li>
	<li><code>1 &lt;= strs[i].length &lt;= 300</code></li>
	<li><code>strs[i]</code> consists of lowercase letters only.</li>
	<li>All words in <code>strs</code> have the same length and are anagrams of each other.</li>
</ul>

struct Node 
{
    string val; 
    int intVal; 
    Node(const string& _val, int _intVal): val(_val),intVal(_intVal){} 
    vector<Node*> vAdjNodes; 
};
class Solution {
public:
    bool isSimilar(const string& s1, const string& s2)
    {
        vector<int> vDiff; 
        for (int idx = 0; idx < s1.length(); idx++)
        {
            if (s1[idx] != s2[idx])
            {
                if (vDiff.size() == 2)
                {
                    return false;
                }
                vDiff.push_back(idx);
            }
        }
        if ((vDiff.size() == 2) || (vDiff.size() == 0))
        {
            return true;
        }
        return false;
    }
    enum class VisitState 
    {
        VISITED,
        NOT_VISITED,
        VISITING
    };
    void bfs(vector<Node*>& vNodes, vector<VisitState>& vVisited, Node* startNode)
    {
        deque<Node*> dqNodes;
        dqNodes.push_back(startNode);
        vVisited[startNode->intVal] = VisitState::VISITING;

        while (!dqNodes.empty())
        {
            auto curNode = dqNodes.front();
            dqNodes.pop_front();
            vVisited[curNode->intVal] = VisitState::VISITED;
            cout << "CN" << curNode->val << endl;

            for (auto adjNode: curNode->vAdjNodes)
            {
                cout << "SOMETHING" << adjNode->val << " " << adjNode->intVal << endl;
                if (vVisited[adjNode->intVal] == VisitState::NOT_VISITED)
                {
                    cout << "PUSHED" << endl;
                    dqNodes.push_back(adjNode);
                    vVisited[adjNode->intVal] = VisitState::VISITING;
                }
            }
        }
    }

    int fullBFS(vector<Node*>& vNodes)
    {
        vector<VisitState> vVisited(vNodes.size(), VisitState::NOT_VISITED); 
        deque<Node*> dqNodes;
        int connComp = 0;

        for (int idx = 0; idx < vNodes.size(); idx++)
        {
            if (vVisited[idx] == VisitState::NOT_VISITED)
            {
                cout << "HERE" << endl;
                bfs(vNodes, vVisited, vNodes[idx]);
                connComp ++;
            }
        }
        return connComp;
    }

    int numSimilarGroups(vector<string>& strs) {
        // Create a graph by mapping each string to a node and an edge if two strings are similar. 
        // You can check simiarity by checking how many letters differ and if they have the same letters.
        // Then just BFS to get the connected components. 
        vector<Node*> vNodes(strs.size(), nullptr); 
        for (int idx = 0; idx < vNodes.size(); idx++)
        {
            vNodes[idx] = new Node(strs[idx], idx);
        }

        for (int idx1 = 0; idx1 < strs.size(); idx1++)
        {
            for (int idx2 = idx1 + 1; idx2 < strs.size(); idx2++)
            {
                string& s1 = vNodes[idx1]->val;
                string& s2 = vNodes[idx2]->val;
                if (isSimilar(s1, s2))
                {
                    cout << s1 << " " << s2 << endl;
                    vNodes[idx1]->vAdjNodes.push_back(vNodes[idx2]);
                    vNodes[idx2]->vAdjNodes.push_back(vNodes[idx1]);
                }
            }
        }
        int connComp = fullBFS(vNodes);
        return connComp;
    }
};
39501