题目描述

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

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

输入格式:
输入第一行是一个正整数 T (1≤T≤5)，表示数据的组数。

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

接下来的 M 行，每行给出一条边两个端点的顶点编号。注意：顶点编号从 1 开始，并且题目保证任何边不会重复给出，且没有自环。

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

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

样例

输入样例:
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

算法1

(拓扑排序) $O(n+m)$

首先用拓扑排序将非环的各个节点入度变为<=0，非章鱼环的特例是共轭环（一个点连多个环），遍历每个点，如果度不是2，且大于1说明是共轭环点，dfs一遍，将ans,cnt清空，剩下的就是有章鱼环的情况，遍历每个点，判断连通性，如果ans>1说明有多个章鱼环，此时应该输出No ans个数

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int> e[N];
int d[N];
int cnt,ans;
int n,m;
void dfs(int x){
    d[x]=0;
    cnt++;
    for(auto y:e[x]){
        if(d[y]){
            dfs(y);
        }
    }
}
void topsort(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(d[i]==1){
            q.push(i);
        }
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        d[t]--;
        for(auto j:e[t]){
            d[j]--;
            if(d[j]==1){
                q.push(j);
            }
        }
    }
}
void solve(){
    memset(d,0,sizeof d);

    cin>>n>>m;

    while(m--){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
        d[x]++;
        d[y]++;
    }
    topsort();

    //多环共点 
    for(int i=1;i<=n;i++){
        if(d[i] && 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;
    }
    for(int i=1;i<=n;i++){
        e[i].clear();
    }
}
int main()
{
    int t; cin >> t;
    while(t --) solve();
    return 0;
}