上海做网站的哪家好,wordpress自动易语言,盐城做百度网站,哔哩哔哩免费观看入口题目
对于无向图 G(V,E)#xff0c;我们将有且只有一个环的、大于 2 个顶点的无向连通图称之为章鱼图#xff0c;因为其形状像是一个环#xff08;身体#xff09;带着若干个树#xff08;触手#xff09;#xff0c;故得名。
给定一个无向图#xff0c;请你判断是不…题目
对于无向图 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 做法
并查集判环。
#includebits/stdc.h
using namespace std;
int n,m,t;
int fa[100010];
int huan[100010];//每个连通块环的数量
int ans;
int dis[100010];//环的长度
vectorint 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);
}
queueint q;
int main(){cint;while(t--){ans0;scanf(%d%d,n,m);for(int i1;in;i) g[i].clear(),fa[i]i,huan[i]0,dis[i]0;for(int i1;im;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)];sta,edb;}else{huan[getfa(b)]huan[getfa(a)];//不可以先setfa不然根就不是原来的根了 setfa(a,b);}}for(int i1;in;i){if(getfa(i)ihuan[i]1){//看有多少个 连通块 是环为1的 ans;}}if(ans!1) {coutNo ansendl;continue;}dis[st]1;//算环的长度 q.push(st);while(!q.empty()){int tmpq.front();q.pop();for(int i0;ig[tmp].size();i){if(dis[g[tmp][i]]) continue;//算过了 if(tmpstg[tmp][i]ed) continue;//头连尾的那条边 q.push(g[tmp][i]);dis[g[tmp][i]]dis[tmp]1;}}coutYes dis[ed]endl;}
}
