主要题型：并查集

题目解析：

T1：Secret Passwords

题意：

给定 $n$ 个由小写字母组成的密码字符串。如果两个密码包含相同的字母，或者通过其他密码产生传递关系，则它们等价。等价关系具有传递性（即若 $a$ 与 $b$ 等价，$b$ 与 $c$ 等价，则 $a$ 与 $c$ 等价）。求这 $n$ 个密码最终能划分出多少个不同的等价类。

思路：

用并查集，因为字符串数量大，直接两两比较会超时，但字母只有 26 个，所以可以将字母作为桥梁，从而建立等价关系。遍历每个字符串，将字符串中出现的所有字母在并查集中两两合并。 然后统计等价类数量。处理完所有字符串后，统计 26 个字母中有多少个是各自集合的根节点（即 Find(i) == i），则这个数量就是不同的等价类数量。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int root[30], vis[30];
int Find(int x) 
{
    if (x != root[x])
    {
        root[x] = Find(root[x]);
    } 
    return root[x];
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i <= 27; i++)
    {
        root[i] = i;
    } 
    for (int i = 1; i <= n; i++) 
    {
        string s;
        cin >> s;
        int siz[30] = {0};
        for (int j = 0; j < s.size(); j++) 
        {
            int now = s[j] - 'a' + 1;
            siz[now]++;
            vis[now] = 1;
        }
        for (int j = 1; j <= 26; j++) 
        {
            if (!siz[j]) continue;
            for (int k = 1; k <= 26; k++) 
            {
                if (!siz[k]) continue;
                int fu = Find(j), fv = Find(k);
                if (fu != fv) root[fu] = fv;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= 26; i++) 
    {
        if (vis[i] && i == Find(i))
        {
            ans++;
        } 
    }
    
    cout << ans << endl;
    return 0;
}

T2：Cthulhu

题意：

给定一个无向图，判断它是否是一个“克苏鲁”图。克苏鲁图的定义为：由一个简单环和至少三棵有根树组成，且这些树的根节点都连接在这个简单环上。如果是，输出 FHTAGN!，否则输出 NO。

思路：

DFS和建图 1.根据图论性质，合法的克苏鲁图必须满足总边数等于总点数，如果 $m \neq n$，直接输出 NO。 2.用DFS遍历建图：将输入的边存入邻接表，然后从任意一个节点出发，使用 DFS 递归遍历其所有相邻节点，并用 vis 数组标记已访问过的节点。 3.连通性判断：DFS 结束后，检查 vis 数组。如果存在未被访问的节点，说明图不连通，输出 NO。 4.如果图连通且 $m = n$，在简单图中它必然是一个合法的基环树（环长 $\ge 3$ 且挂着树），直接输出 FHTAGN!。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
vector<int> g[N];
bool vis[N];
int n, m;
// DFS 判断连通性
void dfs(int u) 
{
    vis[u] = true;
    for (int v : g[u]) 
    {
        if (!vis[v]) 
        {
            dfs(v);
        }
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    //边数必须等于点数
    if (m != n) 
    {
        cout << "NO" << endl;
        return 0;
    }
    // 建图
    for (int i = 0; i < m; i++)
      {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // 判断是否连通
    dfs(1);
    for (int i = 1; i <= n; i++) 
    {
        if (!vis[i]) 
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "FHTAGN!" << endl;
    return 0;
}

T3：Cyclic Components

题意：

给定一个包含 $n$ 个点和 $m$ 条边的无向图，保证无重边和自环。要求找出该图所有连通块中，恰好构成“环”的连通块的个数。根据题目定义，一个连通块是环的充要条件是：该连通块内的点数等于边数，且点数至少为 3。

思路：

BFS 1.遍历连通块：使用 BFS 和队列遍历图，每次从一个未访问过的节点出发，遍历整个连通块。 2.在 BFS 过程中，记录当前连通块包含的节点数量。同时，将该连通块内所有节点的度数累加，由于无向图的一条边会被两个端点各计算一次，因此连通块内的实际边数 b = 总度数 / 2。 3.判断是否为纯环：遍历完一个连通块后，必须同时满足以下三个条件才算作环：

• p >= 3（点数至少为 3）
• p == b（点数等于边数）
• 连通块内所有点的度数都恰好为 2（这是最关键的条件，用于排除“环上挂树枝”的基环树结构） 4.处理所有连通块：重复上述过程直到所有节点都被访问过，最后输出答案。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> g[N];
bool vis[N];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; i++) 
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) 
    {
        if (!vis[i]) 
        {
            int p = 0, d = 0; // p: 点数, d: 度数总和
            bool f = true;  
            queue<int> q;
            q.push(i);
            vis[i] = true;
            while (!q.empty()) 
            {
                int u = q.front();
                q.pop();
                p++;       
                d += g[u].size(); 
                if (g[u].size() != 2) 
                {
                    f = false;
                }
                for (int v : g[u]) 
                {
                    if (!vis[v]) 
                    {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
            int b = d / 2; // 真实的边数
            if (f && p >= 3 && p == b) 
            {
                ans++;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

T4:Edgy Trees