【拓扑剪枝+深搜剪枝/计数】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,didx = 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;
}