题目描述

我们定义一种特殊的无向连通图，称为 章鱼图 (Octopus Graph)：
1. 顶点数大于 2。
2. 图中 有且仅有 一个环。

这种图的形状像一个环（章鱼的身体）以及附着在环上的一些树形结构（章鱼的触手）。

给定一个无向图 $G=(V,E)$。我们需要判断在这个图中，是否存在 有且仅有 一个 章鱼子图。

这里的“章鱼子图”指的是满足章鱼图性质的 极大连通子图。换句话说，我们需要检查图 $G$ 的所有连通分量，看其中是否恰好只有一个连通分量满足章鱼图的定义。

输入格式

• 第一行一个整数 $T$，表示测试数据组数。
• 每组数据：
  • 第一行两个整数 $N, M$，表示图的点数和边数。
  • 接下来 $M$ 行，每行两个整数 $u, v$，表示顶点 $u$ 和 $v$ 之间有一条边（顶点编号从 1 开始）。
  • 保证没有自环和重边。

输出格式

对于每组数据：
如果图中恰好只有一个章鱼子图，输出 Yes 和该章鱼子图中 环的大小（环上的顶点数），用空格隔开。
否则（零个或多个章鱼子图），输出 No 和图中章鱼子图的 数量，用空格隔开。

数据范围

• $1 \le T \le 5$
• $1 \le N, M \le 10^5$

样例

输入:
3
10 10
1 3
3 5
5 7
7 9
1 2
2 4
2 6
3 8
9 10
1 9
10 10
1 3
3 5
5 7
7 9
9 1
1 2
2 4
4 8
8 10
10 1
10 10
1 3
3 5
5 7
7 9
9 1
2 4
4 8
8 10
10 2
10 6

输出:
Yes 5
No 0
No 2

算法 (连通分量 + 图的性质 + 拓扑排序思想)

$O(T \times (N+M))$

思路分析

1. 章鱼图的核心性质:
   一个无向连通图包含 有且仅有 一个环，当且仅当该连通图的 顶点数 V 等于边数 E。

   • 证明: 一个连通图是树当且仅当 $E = V - 1$。向树中添加一条边会恰好创建一个环，此时边数变为 $(V-1)+1 = V$。如果再添加边 ($E > V$)，则会形成更多的环。如果 $E < V-1$，图不连通。如果 $E=V-1$，图是树，没有环。
   • 因此，一个连通分量是章鱼图（且顶点数 > 2）的必要条件是 $V = E$ 且 $V > 2$。这个条件也是充分的。

2. 识别章鱼子图 (极大连通子图):
   题目要求我们找的是满足章鱼图性质的“极大连通子图”，这其实就是图的连通分量。我们需要做的是：
   a. 找出给定图的所有连通分量。
   b. 对于每个连通分量，计算其包含的顶点数 $V_c$ 和边数 $E_c$。
   c. 判断该连通分量是否满足章鱼图的条件：$V_c > 2$ 且 $V_c = E_c$。
   d. 统计满足条件的连通分量的数量 ocnt。

3. 找出连通分量及统计 V 和 E:

   • 可以使用 广度优先搜索 (BFS) 或 深度优先搜索 (DFS) 来遍历图并找出所有连通分量。
   • 维护一个 vis 数组来标记顶点是否被访问过，并记录每个顶点所属的连通分量编号 (cid)。
   • 对于每个连通分量 c，在遍历过程中统计其顶点数 vcnt[c]。
   • 同时，我们需要统计每个连通分量内部的边数 ecnt[c]。一种简单的方法是：在找到所有连通分量后，再次遍历 输入的所有边 (u, v)。对于每条边，确定其所属的连通分量 c = vis[u] - 1 (因为 vis 存的是 cid+1)，然后将 ecnt[c] 加一。

4. 统计章鱼子图数量:

   • 遍历所有连通分量 c (从 0 到 cid-1)。
   • 如果 vcnt[c] > 2 且 vcnt[c] == ecnt[c]，则该分量是一个章鱼子图。将章鱼子图计数器 ocnt 加一。
   • 记录下那个唯一的章鱼子图的 cid (如果 ocnt 最终为 1)。

5. 处理输出:

   • 如果 ocnt == 1，我们需要找到这个章鱼子图的环的大小。转到步骤 6。
   • 如果 ocnt != 1，输出 “No” 和 ocnt。

6. 计算环的大小 (当 ocnt == 1 时):

   • 设唯一的章鱼子图的组件 ID 为 ocid。
   • 这个章鱼子图由一个环和附着在环上的一些树（触手）组成。
   • 环上的点在子图内部的度数至少为 2。而触手上的非连接点（叶子节点）度数为 1。
   • 我们可以通过类似拓扑排序中不断移除度为 1 节点的方法来“剪掉”所有的触手，最后剩下的就是环上的节点。
   • 具体步骤:
     a. 获取该章鱼子图包含的所有顶点 vs = verts[ocid]。
     b. 计算每个顶点 u 在该子图内部的度数 deg[u]。遍历 u 的所有邻居 v，如果 v 也属于同一个子图 (vis[v] == ocid + 1)，则 deg[u] 加一。
     c. 初始化一个队列 q，将所有子图内度数为 1 的顶点（触手的叶子节点）加入队列。
     d. 维护一个 rem 数组标记已被移除（剪掉）的顶点，以及一个计数器 rmcnt 记录移除的顶点数。
     e. 当队列不为空时：
     i. 出队一个顶点 u。
     ii. 遍历 u 的所有邻居 v（必须在子图内且未被移除）：
     * 将 v 的度数 deg[v] 减一。
     * 如果 deg[v] 变为 1，说明 v 现在成为了新的叶子节点，将其加入队列 q，标记 rem[v] = true，并增加 rmcnt。
     f. 循环结束后，所有触手上的顶点都被移除了。总顶点数 vtotal = vcnt[ocid]，移除的顶点数是 rmcnt。
     g. 环上的顶点数 cyc = vtotal - rmcnt。
   • 输出 “Yes” 和 cyc。

时间复杂度

1. 找出连通分量: 使用 BFS 或 DFS 遍历所有顶点和边一次，复杂度为 $O(N+M)$。
2. 统计边数: 遍历所有 $M$ 条边一次，复杂度为 $O(M)$。
3. 识别章鱼子图: 遍历所有连通分量（最多 $N$ 个），检查 $V_c$ 和 $E_c$，复杂度为 $O(N)$。
4. 计算环大小 (如果需要):
   • 计算子图内度数：遍历子图的顶点和边，复杂度最多 $O(N+M)$。
   • 拓扑排序剪枝：每个顶点和边最多处理一次，复杂度 $O(N+M)$。
5. 整个过程对每组测试数据是线性的。
6. 总时间复杂度为 $O(T \times (N+M))$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (本题未使用)

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; // 测试数据组数
    cin >> T;
    while (T--) { // 处理每组测试数据
        int N, M; // 顶点数 N, 边数 M
        cin >> N >> M;

        // g: 邻接表存储图 (使用 1-based 索引)
        vector<vector<int>> g(N + 1);
        // vis[i]: 顶点 i 的访问状态/所属连通分量编号 (0:未访问, >0:已访问, 值为 cid+1)
        vector<int> vis(N + 1, 0);
        // vcnt: 存储每个连通分量的顶点数
        vector<int> vcnt;
        // ecnt: 存储每个连通分量的边数
        vector<int> ecnt;
        // verts: 存储每个连通分量包含的顶点列表
        vector<vector<int>> verts;
        // edges: 存储所有输入的边，用于后续计算 ecnt
        vector<pair<int, int>> edges;

        // 读入边，构建邻接表和边列表
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
            edges.push_back({u, v});
        }

        int cid = 0; // 当前连通分量编号 (从 0 开始)
        // 遍历所有顶点，查找连通分量
        for (int i = 1; i <= N; i++) {
            if (vis[i] == 0) { // 如果顶点 i 未被访问过，说明找到一个新的连通分量
                queue<int> q; // 使用 BFS 查找连通分量
                q.push(i);
                vis[i] = cid + 1; // 标记访问，并记录分量编号
                int vc = 0;       // 当前分量的顶点计数
                vector<int> vl;   // 当前分量的顶点列表

                // BFS 过程
                while (!q.empty()) {
                    int u = q.front();
                    q.pop();
                    vc++;          // 增加顶点计数
                    vl.push_back(u); // 将顶点加入列表

                    // 遍历邻居
                    for (int v : g[u]) {
                        if (vis[v] == 0) { // 如果邻居未访问
                            vis[v] = cid + 1; // 标记访问
                            q.push(v);      // 加入队列
                        }
                    }
                }

                // 存储该连通分量的信息
                vcnt.push_back(vc);      // 顶点数
                verts.push_back(vl);     // 顶点列表
                ecnt.push_back(0);       // 初始化边数为 0
                cid++;                   // 增加连通分量编号
            }
        }

        // 遍历所有边，统计每个连通分量内部的边数
        for (auto [u, v] : edges) {
            int c = vis[u] - 1; // 获取顶点 u 所属的分量编号 (0-based)
            // 确保 c 是有效的编号 (理论上 u, v 必在同一分量)
            if (c >= 0 && c < cid) {
                ecnt[c]++; // 增加该分量的边数
            }
        }

        int ocnt = 0;   // 章鱼子图的数量
        int ocid = -1; // 存储唯一的章鱼子图的编号 (如果存在)

        // 遍历所有连通分量，判断是否为章鱼子图
        for (int c = 0; c < cid; c++) {
            // 条件：顶点数 > 2 且 顶点数 == 边数
            if (vcnt[c] > 2 && vcnt[c] == ecnt[c]) {
                ocnt++;   // 找到一个章鱼子图
                ocid = c; // 记录其编号
            }
        }

        // 根据章鱼子图的数量输出结果
        if (ocnt == 1) { // 如果恰好只有一个章鱼子图
            int tc = ocid;               // 获取该章鱼子图的编号
            vector<int>& vs = verts[tc]; // 获取其顶点列表
            vector<int> deg(N + 1, 0);   // 存储子图内每个顶点的度数
            vector<bool> rem(N + 1, false); // 标记顶点是否在剪枝过程中被移除

            // 计算子图内每个顶点的度数
            for (int u : vs) {
                for (int v : g[u]) {
                    // 只有邻居 v 也在同一个子图内时才计入度数
                    if (vis[v] == tc + 1) {
                        deg[u]++;
                    }
                }
            }

            queue<int> q;          // 队列用于拓扑排序剪枝
            int vtotal = vcnt[tc]; // 子图总顶点数
            int rmcnt = 0;         // 被移除的顶点数 (触手上的点)

            // 初始化队列：将所有度数为 1 的点加入队列
            for (int u : vs) {
                if (deg[u] == 1) {
                    q.push(u);
                    rem[u] = true; // 标记为移除
                    rmcnt++;
                }
            }

            // 拓扑排序剪枝过程
            while (!q.empty()) {
                int u = q.front();
                q.pop();

                // 遍历被移除节点 u 的邻居 v
                for (int v : g[u]) {
                    // 只考虑在同一子图内且未被移除的邻居
                    if (vis[v] == tc + 1 && !rem[v]) {
                        deg[v]--; // 将邻居 v 的度数减 1
                        if (deg[v] == 1) { // 如果 v 的度数变为 1
                            q.push(v);     // 将 v 加入队列
                            rem[v] = true; // 标记 v 为移除
                            rmcnt++;
                        }
                    }
                }
            }

            // 计算环的大小 = 总顶点数 - 触手上的顶点数
            int cyc = vtotal - rmcnt;
            cout << "Yes " << cyc << "\n"; // 输出 Yes 和环的大小
        } else { // 如果章鱼子图数量不为 1
            cout << "No " << ocnt << "\n"; // 输出 No 和章鱼子图的数量
        }
    }

    return 0; // 程序正常结束
}