输出
如果存在符合条件的连线,则输出"Yes",
如果不存在符合条件的连线,输出"No"。
样例输入
2
4 3
1 2
1 3
1 4
4 5
1 2
2 3
1 3
1 4
3 4
样例输出
No
Yes
#includeusing namespace std;int n,m;int du[2000],fun[2000],sum[2000];int find(int x){ if(x!=fun[x]) return fun[x]=find(fun[x]); return x;}void connect(int x,int y){ int a=find(x),b=find(y); if(a!=b) { fun[a]=b; sum[b]+=sum[a]; }}int main(){ int t,i,j,x,y,cnt; cin>>t; while(t--) { cin>>n>>m; for(i=0; i<=n; i++) { fun[i]=i; sum[i]=1; du[i]=0; } for(i=0; i>x>>y; du[x]++; du[y]++; connect(x,y); } cnt=0;//统计奇度数的点。 for(x=i=1; i<=n; i++) { if(du[i]%2)cnt++; else x=i; } if((cnt==0||cnt==2)&&sum[find(x)]==n) cout<<"Yes"<典型的,并查集,http://baike.baidu.com/view/566040.htm
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
暂时没有评论,来抢沙发吧~