【拓扑剪枝+深搜剪枝/计数】2024睿抗-章鱼图的判断

题目描述

对于无向图 $G=(V,E)$，我们将有且只有一个环的、大于 $2$ 个顶点的无向连通图称之为章鱼图，因为其形状像是一个环（身体）带着若干个树（触手），故得名。

给定一个无向图，请你判断是不是只有一个章鱼子图存在。

注意：这里的章鱼子图指的是满足章鱼图性质的极大连通子图。

输入格式

输入第一行是一个正整数 $T$，表示数据的组数。

每组数据的第一行是两个正整数 $N,M$，表示给定的无向图有 $N$ 个点，$M$ 条边。

接下来的 $M$ 行，每行给出一条边两个端点的顶点编号。

注意：顶点编号从 $1$ 开始，并且题目保证任何边不会重复给出，且没有自环。

输出格式

对于每组数据，如果给定的图里只有一个章鱼子图，则在一行中输出 Yes 和章鱼子图环的大小（及环中顶点数），其间以 $1$ 个空格分隔。

否则，则在一行中输出 No 和图中章鱼子图的个数，其间以 $1$ 个空格分隔。

数据范围

$$\begin{gathered} 1 \\ leT \\ le5 \end{gathered}$$,
$$\begin{gathered} 1 \\ leN,M \\ le10^5 \end{gathered}$$

输入样例：

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

拓扑剪枝+深搜剪枝/计数

通过拓扑排序剥离无向图中的非环结构（“触手”），再通过DFS检测并统计剩余环的数量和大小，最终判断图中是否存在单一标准环（所有节点度数为2的连通环）或多个非常规环结构。

C++ 代码

/*
拓扑排序变种：以度数为衡量标准
    topsort 之效为剥除环之外的树状结构（谓之触手），留环（谓之头部）
    但须思忖余环呈多环嵌套或多环线连须去除
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10,M = 1e5 + 10;
int h[N],e[2*M],ne[2*M],idx;
int d[N]; // 记录结点度数
int n,m;
int cnt,ans;

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

void topsort(){
    // 初始化队列
    queue<int> q;
    // 度0/1入队
    for(int i=1;i<=n;i++){
        if(d[i] == 1) q.push(i);
    }
    // 取队首，（归序），削邻度
    // 度0/1入，周而复始，队空则成
    while(!q.empty()){
        int t=q.front();
        q.pop();
        // 度数要变化！！
        d[t]--;
        for(int i=h[t]; ~i ; i = ne[i]){
            int j=e[i];
            if(--d[j] == 1) q.push(j);
        }
    }
}

// 清除环并且记录环结点数
void dfs(int u){
    cnt ++;
    d[u]=0; // 清空当前节点的度数
    
    for(int i=h[u];~i;i=ne[i]){
        if(d[e[i]]) dfs(e[i]);
    }
}


void solve(){
    cin>>n>>m;
    // 清空 idx,h,d
    idx = 0;
    memset(h,-1,sizeof h);
    memset(d,0,sizeof d);
    // 初始化
    while(m--){
        int x,y;
        cin>>x>>y;
        add(x,y);add(y,x);
        d[x]++;d[y]++; // 度数加1
    }
    // topsort去除所有的非环
    topsort();
    // 去除所有的特异环
    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;
}