1. 先对该图做一遍拓扑排序算法
2. 做完拓扑排序算法之后遍历度数组d，如果d[i] > 0 and d[i] != 2，说明i这个点所在的极大连通子图有多个环，所以这个极大连通子图不满足章鱼图性质中的只有一个环，dfs(i)将i这个点所在的极大连通子图的所有点的d[]都置为0
3. 第二步做完后，剩下的d[i] == 2的点所在的极大连通子图就都是只有一个环的了，即满足章鱼图性质，即该极大连通子图就是章鱼图。遍历数组d，如果d[i] == 2，则ans ++（ans记录有多少个章鱼子图），并且dfs(i)，将i这个点所在的极大连通子图的所有点的d[]都置为0，防止ans加了多次。

T = int(input())

def topsort():
    hh = 0;tt = -1
    q = [0] * N
    for i in range(1,n + 1):
        if d[i] == 1: # 将度为1的点都加入队列中
            tt += 1
            q[tt] = i
    while hh <= tt:
        t = q[hh]
        hh += 1

        d[t] -= 1 # 删去该点的出度。无向图要有这一行代码，有向图不用

        i = h[t]
        while i != -1:
            j = e[i]
            d[j] -= 1 # 删除点t指向点j的边
            if d[j] == 1: # 如果点j的入度为1了,就将点j入队
                tt += 1
                q[tt] = j
            i = ne[i]

cnt = 0
def dfs(u):
    global cnt
    cnt += 1
    d[u] = 0

    i = h[u]
    while i != -1:
        j = e[i]
        if d[j]:
            dfs(j)
        i = ne[i]

while T:
    T -= 1

    n,m = map(int,input().split())

    N = n + 10;M = (m + 10) * 2

    h = [-1] * N;e = [0] * M;ne = [0] * M;idx = 0
    d = [0] * N

    def add(a,b):
        global idx
        e[idx] = b;ne[idx] = h[a];h[a] = idx;idx += 1

    for i in range(m):
        x,y = map(int,input().split())
        add(x,y);add(y,x)
        d[x] += 1
        d[y] += 1

    topsort()

    """
    做完拓扑排序算法之后遍历度数组d，如果`d[i] > 0 and d[i] != 2`，
    说明`i`这个点所在的极大连通子图有多个环，所以这个极大连通子图不满足章鱼图性质中的
    只有一个环，`dfs(i)`将`i`这个点所在的极大连通子图的所有点的`d[]`都置为0
    """
    for i in range(1,n + 1):
        if d[i] > 0 and d[i] != 2:
            dfs(i)

    ans = 0
    cnt = 0
    """
    剩下的`d[i] == 2`的点所在的极大连通子图就都是只有一个环的了，即满足章鱼图性质，
    即该极大连通子图就是章鱼图。遍历数组d，如果`d[i] == 2`，则`ans ++`
    （`ans`记录有多少个章鱼子图），并且`dfs(i)`，将`i`这个点所在的极大连通子图的所有点的`d[]`都置为0，防止`ans`加了多次。
    """
    for i in range(1,n + 1):
        if d[i] == 2:
            dfs(i)
            ans += 1

    if ans == 1:
        print(f'Yes {cnt}')
    else:
        print(f'No {ans}')

python代码会超时，该为C++代码就可以AC了

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;
const int M = 200010; 
int h[N], e[M], ne[M], d[N]; 
int q[N]; 
int idx; 
int cnt, ans;


void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}


void topsort(int n) {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 1) { // 将所有度为1的点加入队列
            q[++tt] = i;
        }
    }

    while (hh <= tt) {
        int t = q[hh++];
        d[t]--; // 删除该点的出度

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j]--; // 删除边
            if (d[j] == 1) { // 如果邻接点度数变为1，加入队列
                q[++tt] = j;
            }
        }
    }
}


void dfs(int u) {
    cnt++; 
    d[u] = 0; 

    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (d[j]) {
            dfs(j);
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    memset(h, -1, sizeof h);
    memset(d, 0, sizeof d);
    idx = 0;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
        d[x]++;
        d[y]++;
    }

    topsort(n);

    for (int i = 1; i <= n; i++) {
        if (d[i] > 0 && d[i] != 2) {
            dfs(i);
        }
    }

    ans = cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (d[i] == 2) {
            dfs(i);
            ans++;
        }
    }

    if (ans == 1) {
        cout << "Yes " << cnt << endl;
    } else {
        cout << "No " << ans << endl;
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}