河北建筑工程信息网站海南最新消息今天

题目

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

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

输入格式:

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

每组数据的第一行是两个正整数 N,M (1≤N,M≤105)，表示给定的无向图有 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

做法

并查集判环。

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int fa[100010];
int huan[100010];//每个连通块环的数量 
int ans;
int dis[100010];//环的长度 
vector<int> g[100010];//存边 
int st,ed;//环的头和尾 
int getfa(int x){if(fa[x]==x) return x;return fa[x]=getfa(fa[x]);
}
void setfa(int x,int y){fa[getfa(x)]=getfa(y);
}
queue<int> q;
int main(){cin>>t;while(t--){ans=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) g[i].clear(),fa[i]=i,huan[i]=0,dis[i]=0;for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);g[a].push_back(b);g[b].push_back(a);if(getfa(a)==getfa(b)) {//环出现 huan[getfa(a)]++;st=a,ed=b;}else{huan[getfa(b)]+=huan[getfa(a)];//不可以先setfa，不然根就不是原来的根了 setfa(a,b);}}for(int i=1;i<=n;i++){if(getfa(i)==i&&huan[i]==1){//看有多少个 连通块 是环为1的 ans++;}}if(ans!=1) {cout<<"No "<<ans<<endl;continue;}dis[st]=1;//算环的长度 q.push(st);while(!q.empty()){int tmp=q.front();q.pop();for(int i=0;i<g[tmp].size();i++){if(dis[g[tmp][i]]) continue;//算过了 if(tmp==st&&g[tmp][i]==ed) continue;//头连尾的那条边 q.push(g[tmp][i]);dis[g[tmp][i]]=dis[tmp]+1;}}cout<<"Yes "<<dis[ed]<<endl;}
}